This train is cancelled because of political crisis between Russia and Georgia (as I think, because the route was on rebel territories, and this was definitely done according to the orders from Russian president).
For now air and automobile connections are started to being reestablished, but not the train.
All you can do - use the train to the Baku (Sorry, only a Russian site) - there is no border problem when using it, and there are trains from Baku to Tbilisi.
Armenia had no borders with Russia, and I don't think you should use trains to Yerevan.
Update:
About the old trains. I found this map of USSR rail roads. According to it the only railroad for the route was via Sukhumi, so for now it is closed, and there is not any chance Russia and Georgia will create a new one in the near future. There was a narrow gauge railway between Tskhinvali and Vladikavkaz, and it is closed now too.
Another update:
About the rest part of the railroad - yes, you can use it, and for now there is a train between Moscow and Sukhumi (the capital of Abkhazia), which uses exactly the same railroad.