OK, I can answer a good part of this.
From Europe, you can get into Russia fairly simply with a visa - tourist visa is for 1 month max, however, which is a bit limiting (maybe not for you, but it was for me).
From there I went south and into Kazakhstan, across Uzbekistan, into Tajikistan. Afterwards I continued north - Kyrgyzstan, Kazakhstan, back into Russia and across to Mongolia. All of this was done with public transport - trains are great in Russia, are OK in Kazakhstan if you can get on one, iffy in Uzbekistan when they're running and mostly non-existent in Tajikistan and Kyrgyzstan (although China wants to connect the one track in Kyrgyzstan with the Chinese rail system).
Most of the travel was on trains in Russia, and then shared taxis, minibuses, walking and 4WD taxis in the other 'stans.
'What is safe' is always subjective - I could argue that nowhere is safe, or that anywhere is safe. However, follow the usual safety tips, and keep EVERY SINGLE PIECE OF DOCUMENTATION for unscrupulous border guards, security guards, dodgy police and militia who will often look for a way to get some cash off you. See Tactics to Avoid Getting Hassled by Corrupt Police for some more information on that fun aspect of travelling in the area.
From Kyrgyzstan and Tajikistan there are ways out into China, so you could do that, and then travel south.
However, I did all this in the heat of summer. There will be some road closures especially at altitude in Tajikistan over winter. Trains should still get you to China via Kazakhstan if you so wanted (Urumqi seems to be the place to aim for in China). I'd personally wait until warmer months if possible, having flown over the area as late as April and still been amazed at the gigantic frozen lakes in Kazakhstan!
