You will end up paying quite alot to go by road because you will need to hire a driver/tour guide. The borders in these areas change their regulations too. There is/was a crossing into China which leads to a town called Barkol, and then onto Urumqi. Depending on who you ask, you need a Chinese tour agent hired to meet you at the China side if you are crossing into China from Mongolia. But, I met some Americans who did this same crossing last summer (2012) with no need for this pre-arranged driver/guide. Then the Russian side... it may very well be "closed". You just never know. Suffice to say, you can plan all you want from the other side of the planet, but until you land in Mongolia, or China, or Russia, you never know what will happen. Even if you manage to plan something and have arrangements before you leave, these could all change by the time you get out there!
It would be prudent to get a multiple entry China tourist visa, 6 months, as well as a multiple entry Russia visa, and whatever visa you can get for Mongolia. Despite my warnings above, you can get these sorts of visa while in your home county. Don't get single entry tourist visas. If you get single entry, and you hire a car to the border, and the Mongol side processes you, but the Russian side won't let you in, then how do you get back into Mongolia? And if you can get back in, you may very well be required to go to Beijing to get the proper papers. But if you used your single entry China visa flying into Beijing in the first place, then you need to try to get another China tourist visa in Ulaanbaatar. But, sometimes this is hard to do, so suddenly you are flying to South Korea! This is no exaggeration.
Get as many visas multiple entry visas for all the countries you will visit. Then come and plot your road trip to Tuva!