A win would be a huge boost for Gordon Strachan's side ahead of Monday's showdown at home to Germany.
Tshkadadze's first two games in charge couldn't have been much harder, though, as they hosted world champions Germany before having to go to Poland, suffering another 4-0 defeat to the group leaders.
They were only 1-0 down after 88 minutes in Warsaw but then let Robert Lewandowski score three to add gloss to the victory.
Georgia have lost five of their six qualifiers, with their only victory coming against the lowest-ranked side in the group, Gibraltar.
At home they are without a competitive win in almost three years and have only scored once in that six-game winless stretch.
They have never qualified for the finals of a major tournament, coming closest to reach the Euro finals the first year they participated in 1996, when they finished third in Group 7.
Recent Euro 2016 qualifying form: LLWLLL
Recent form (all competitions): WLWLLL
Poland and Germany are not out of sight yet and Scotland could finish in one of the top two places that guarantees passage to the finals in France next summer.
Even if they can't overhaul the aforementioned duo, Strachan's men are two points clear of Ireland in the race for third spot, which suggests at least a two-legged playoff.
Scotland have lost just one of their last eight matches and have scored in each of their last 12 internationals, netting 19 total goals in the process.
Their campaign started with a trip to recently-crowned World Cup winners Germany, and the Scots almost stunned the home side before losing out 2-1.
Since then, they have won three out of three at home against Georgia, Ireland and Gibraltar as well as drawing on the road in Poland and Ireland.
Shaun Maloney, who is Scotland's top scorer so far in qualifying, has scored with four of his six shots on target. Only Lewandowski (seven) and Thomas Muller (five) of Poland and Germany respectively have more goals than the Hull City man.
Recent form: LWDWWD
Recent form (all competitions): WLWWWD
Matt Ritchie started the last qualifier against Ireland on the right of midfield and will hope that his recent experience of playing in the Premier League with Bournemouth will see him hold down his place ahead of Ikechi Anya.
Georgia possible starting lineup:
Loria; Lobzhanidze, Kashia, Amisulashvili, Dvali, Navalovski; Okriashvili, Ananidze, Kobakhidze, Qazaishvili; Vatsadze
Scotland possible starting lineup:
Marshall; Hutton, Martin, Mulgrew, Robertson; Ritchie, Brown, Morrison, Maloney; Naismith, Fletcher
Head To Head
Georgia have only ever played Scotland once on home soil and claimed a 2-0 victory in October 2007 in a Euro 2008 qualifier.
We say: Georgia 0-1 Scotland
The Scots were far from convincing in the reverse in Glasgow, but with qualification getting ever closer, Strachan's side won't waste the chance to put the pressure on Poland, Germany and Ireland, who all play later on Friday.