Verein

Lebedenko begann seine Karriere bei Torpedo Moskau. Zur Saison 2002 rückte er in den Profikader Torpedos. Im März 2002 gab er dann gegen den FK Dynamo Moskau sein Debüt in der Premjer-Liga. In seiner ersten Profisaison kam er zu 21 Erstligaeinsätzen, in denen er sechs Tore erzielte. In der Saison 2003 machte er drei Tore in 29 Spielen. In der Saison 2004 gelangen ihm neun Tore in 23 Einsätzen.

Zur Saison 2005 wechselte er innerhalb der Stadt zum Ligakonkurrenten Lokomotive Moskau. Für Lok kam er in seiner ersten Saison zu 23 Einsätzen, in denen er sechsmal traf. Zu Beginn der Saison 2006 spielte der Angreifer dann aber keine Rolle mehr, woraufhin er im Juli 2006 innerhalb der Liga zu Saturn Ramenskoje weiterzog. Für Saturn kam er bis Saisonende zu 21 Einsätzen und fünf Toren. In der Saison 2007 erzielte er zwei Tore in 26 Einsätzen, in der Saison 2008 wurde er nur noch spärlich eingesetzt und kam zu zehn Einsätzen.

Zur Saison 2009 wechselte Lebedenko zum Ligakonkurrenten FK Rostow. Für Rostow kam er in der Saison 2009 zu 29 Einsätzen, lediglich ein Spiel verpasste er gesperrt. In der Saison 2010 absolvierte er dann alle 30 Saisonspiele und erzielte drei Saisontore. Zur Saison 2011/12 schloss sich der Stürmer Rubin Kasan an. Für Rubin kam er bis zur Winterpause zu 22 Einsätzen, in denen er zwei Tore machte.

Im Januar 2012 wechselte er zum Ligakonkurrenten Terek Grosny. Bis zum Ende der Spielzeit spielte er zwölfmal für die Tschetschenen und erzielte zwei Tore. In der Saison 2012/13 kam er zu 27 Einsätzen, in der Spielzeit 2013/14 ebenfalls. In der Saison 2014/15 verpasste er lediglich eine Partie gesperrt und absolvierte die restlichen 29 Saisonspiele. 2015/16 spielte er 25 Mal in der Premjer-Liga, in der Saison 2016/17 kam er 17 Mal für Terek zum Einsatz.

Nach fünfeinhalb Jahren in Grosny kehrte Lebedenko zur Saison 2017/18 in seine Heimatstadt zurück und wechselte zum Drittligisten Ararat Moskau. Für Ararat spielte er 17 Mal in der Perwenstwo PFL. Im Januar 2018 schloss der Angreifer sich dem Zweitligisten FK Fakel Woronesch an. In Woronesch war er von Anfang an Kapitän. In seinem ersten Halbjahr machte er zwölf Partien in der Perwenstwo FNL, in denen er dreimal traf. In der Saison 2018/19 erzielte er 14 Tore in 33 Einsätzen. Damit war er nach Maxim Barsow der zweitbeste Torschütze der FNL.

Zur Saison 2019/20 kehrte Lebedenko zum Ligakonkurrenten Torpedo Moskau zurück. In der COVID-bedingt abgebrochenen Spielzeit kam er zu 27 Zweitligaeinsätzen, in denen er sechsmal traf. In der Saison 2020/21 gelangen ihm zehn Treffer in 36 Einsätzen. In der Saison 2021/22 kam er in allen 38 Partien zum Einsatz und erzielte acht Tore, mit Torpedo stieg er 2022 wieder in die Premjer-Liga auf.

Nationalmannschaft

Lebedenko spielte zwischen 2002 und 2005 21 Mal für die russische U-21-Auswahl. Im Februar 2013 stand er einmal im Kader der A-Nationalmannschaft, für die er aber nie spielen sollte.