What a great idea! I've always dreamed about doing this trip myself, but can't seem to get the time and money necessary. That said, let's see if I can help you out a little bit with my experience in the former USSR.

1) Do NOT travel through Belarus if you can avoid it. It will be cleaner, nicer, easier and faster to travel through the Ukraine. One less visa to worry about as well. Plus the Ukraine route will be far more scenic (the Carpathian Mountains or the great Eastern Bog, your choice). Also, Kiev is really a great European capital and worth visiting.

Also, for Ukraine, you'll be best off buying a ticket to the Ukrainian border and then from there buying a ticket to Kiev. Otherwise you'll have to sit on the border for 2-3 hours while they change the gauge of the train wheels.

1*) I disagree with someone here who posted that you should go through Kaliningrad/Lithuania. Not the best idea since all trains from Vilnius (or anywhere in Lithuania) to Moscow go through Belarus. Avoid getting another visa if you can. That said, if you aren't averse to the cost of a Belarussian transit visa (they cost $131), it might be a bit easier. Plus you could stay for up to 3 days in the unbelievably cheap cities of Minsk and/or Brest.

2) There are plenty of agents ready and willing to sell you Russian train tickets. Ones that I happen to know are www.visatorussia.com or www.traveltorussia.com or www.waytorussia.net or www.expresstorussia.com. The last one is probably the most experienced with Trans-Siberian routes. The only problem with these agencies is that they will try to book you on a 1st or 2nd class ticket (kupejny bilet). A significantly cheaper option, if you can find someone to book it, is the open compartments (platzkartny bilet). The only difference is the number of people in your compartment (1st class - 2, 2nd class - 4, platzkartny - 6 with no door).

You could also just call a Russian travel agent (who might take a smaller fee), but if you don't speak any Russian this might be difficult. If you are a bit more adventurous, you can certainly buy the tickets segment by segment in Moscow and, assuming you're not traveling on holidays, there should be plenty of seats. This is easier with Russian, but certainly not impossible. If you'd like, I'm sure I could give you the e-mail addresses of some American, English-and-Russian-speaking friends of mine in Moscow who could help you get the tickets you need.

I'm no expert on Beijing, however. Though they probably speak English there more frequently than in Russia, so you shouldn't have too much of a problem.

Schastlivogo puti! (Happy traveling!)