Koedinov speelde in de periode 1992–1996 twintig officiële interlands (één doelpunt) voor het Georgisch voetbalelftal[3]. Hij maakte zijn debuut voor de nationale ploeg in de met 1-0 verloren oefeninterland op 2 september1992 tegen Litouwen. Zijn eerste en enige interlandtreffer volgde op 12 februari1994, toen Georgië tijdens een vierlandentoernooi op Malta met 2-0 won van Tunesië. Het andere doelpunt in die wedstrijd kwam op naam van Micheil Kavelasjvili.