Tevdoradze 5 sentyabr 1938-ci ildə Tbilisidə anadan olmuşdur. O, 1960-cı ildə Tbilisi Xarici İnstitutunun Alman dili və ədəbiyyatı fakültəsini bitirmişdir. Tevdoradze 1962–1963-cü illərdə Rustavi şəhərində orta məktəb müəllimi, 1963–1965-ci illərdə yerli komsomolun rəhbəri olmuşdur. O, 1972-ci ildə Tbilisi 3 saylı məktəbin direktor müavini, 1975-ci ildə isə Tbilisinin 90 saylı məktəbinin direktoru vəzifəsinə təyin edilmişdir.

Tevdoradze 1993-cü ildən 2003-cü ildə qurum ləğv olunana qədər üzvü olmuşdur. O vaxtdan Vahid Milli Hərəkatın üzvüdür. O, 1995–2008-ci illərdə Gürcüstan parlamentinin üzvü olmuş, 2004–2013-cü illərdə Əfv üzrə Dövlət Komissiyasının prezidenti olmuşdur. O, həmçinin 2004-cü ildə reintreqasiya işləri üzrə nazir müavini olmuşdur.

Tevdoradze 2008-ci ildə Gürcüstanda parlamentin inkişafına və insan hüquqlarının müdafiəsinə verdiyi şəxsi töhfəyə görə "Şərəf" ordeni ilə təltif edilmişdir.