It looks like it tends not to leave until July, but if you did end up doing it a little later you could bump into a bunch of people along the way doing the Mongol Rally, which leaves from the UK and some spots in Europe, with different teams travelling various routes to end up in Mongolia.
While travelling in the 'stans in 2010 we kept bumping into Mongol Rally people travelling in the opposite direction. Stood in a crowd outside the Kazakh embassy in Tashkent for hours (on day 2 of my attempt to get in to pick up another visa) with a couple of guys doing the rally, then saw a whole bunch congregating in Bukhara, and a few stragglers over near the Aral Sea.
If nothing else, it might be worth trying to get in touch with people who have done that for tips on travelling overland in that direction.
Turkmenistan definitely. Besides all of the other craziness listed above, the Kipchak Mosque is another stopping place there. It’s Niyazov’s Taj Mahal…to himself.
I voted for Kazakhstan. I figure I could fly into Volgograd, Russia, check things out there, then fly into Almaty, and either head south to Bishkek and then Tashkent, or head east towards the mountains. And if I could do it on horseback with a bow strapped to my back, that would be awesome.