First of all I want to say, that all kinds of self-supported touring are alive tradition in our country, they are part of our modern culture.
There are many bike touring clubs in Moscow, Saint Petersburg and in other big cities. They organize weekend cycling, making summer season schedule on their websites. People meet at weekend cycling. They know each other better and then ones makes a long distance tour together.
It is commonly to make tours with a company of 3-8 friends. Such groups of cyclists have got a leader, mechanic, accountant and chronicler. Some of the clubs and companies are less organized, some of them are more. It is possible to choose which of them is suitable.
There are my personal priorities for long bike tour on leave:
1. To enjoy nature - wild camping and minor roads.
2. To get to know about another culture.
3. To combine this with a physical activity.
4. To change surroundings for a while.
5. To refresh our family relations.
6. To get adrenalin in adventures.
7. Acceptable comfort level - shops, roads etc.
These priorities determine my future touring route. Also the season which can I get leave in.
What are your priorities? I do not know which of those above are more important for you. Therefore, I can't give you concrete recommendations.
There are interesting regions for bike touring in Russia:
The historical center of Russia, west and north-west country is best choice for beginners. Less difficult routes are there.
In particular the local roads between Moscow and Saint Petersburg are suitable, the ones between Moscow and Archangelsk as well.
Karelia and Kola Peninsula.
Also South and Medium Urals, Altai, Far East near to Vladivostok, Kamchatka (hotel accommodation only because of bears) are popular.
Comfort and infrastructure decrease in North and East direction. Woods are almost absent in the South, except Caucasus Mountains.
I don't recommend you to visit republics of northern caucasus and republic Kalmykia. I have not been there, but I have got bad information.
Cycling on main roads is not a good idea, especially near to big cities.
Something is worth to see. The best way is to buy a guide-book. I can't describe all this here.
Credit card touring - I have not got such experience.
Wild camping is allowed everywhere but one should be really by stealth, because drunken locals may be importunate and aggressive.
GPRS Internet connection is available near main cities. It is better to use local mobile communication services.
Food - you will not be hungry, I'm sure.
Trains are pretty comfortable, it depends on class. It is allowed to take bike, wrapped in cover, to compartment, but conductor may demand a bribe. I show him regulations in this case. Wheels must be disconnected to reduce luggage size.
Suburb trains are useful too.
Language barrier is a problem, so a phrase-book is helpful.
To get visa is possible. It is a special issue.
I think, that if a man is going to leave western “comfort zone” on his own risk, he should be a little bit adventurer. If this is about you, welcome.