Родился 10 ноября 1922 года в селе Грозное Кировского района Таласской области в семье рабочего. Русский. Образование начальное. С 1931 года воспитывался в детском доме в городе Ростове, а потом в коммуне "Верный путь". В июле 1941 года был призван в армию и направлен в Военно-морскую школу в Сталинград, а затем отправлен в Куйбышевскую область, где формировалась 67-я Морская стрелковая бригада. В ноябре бригада получила назначение на Карельский фронт и в начале 1942 года вступила в боевые действия против 7-й немецкой егерской дивизии. В одном из боев Лебеденко был ранен и обморожен. После лечения в госпитале вернулся в свой 253-й стрелковый полк 45-й стрелковой дивизии, в составе которого прошел боевой путь до Дня Победы.

Демобилизовался 20 ноября 1946 года и вернулся в звании сержанта в город Грозный. 18 лет работал на железной дороге, потом перешел на медико-инструментальный завод наладчиком оборудования. В 1969 году переехал в Калинин, поступил на вагоностроительный завод, где проработал до 1983 года, отсюда ушел на пенсию. Награжден орденом Отечественной войны I степени, медалями "За отвагу", "За оборону Советского Заполярья" и 10 юбилейными медалями. В составе сводного полка Карельского фронта участвовал в Параде Победы 24 июня 1945 года в звании сержанта. В настоящее время живет в г.Твери.

Из воспоминаний:

Вместе с Лебеденко Н.Е. в полку служили воины из Калининской области: Полетаев 1910 г.р. из Кувшиновского района, Ильиных Алексей 1923 г.р. из Рамешковского района, Пуля Афанасий Николаевич 1902 г.р., Жарков 1905 г.р. из Жарковского района. Особенно тяжелые бои дивизия вела в апреле-мае 1942 года. Фашисты упорно оборонялись. Ведя огонь из пулемета, приходилось неоднократно менять огневую позицию. Кончились патроны. Крикнул подносчику, чтобы он нес патроны, а он не реагирует. Подполз, а подносчик сидит у коробок с патронами мертвый. Взял патроны, пополз к пулемету и вновь открыл огонь по врагу. Этот бой продолжался дотемна. Разорвавшейся миной был тяжело ранен и эвакуирован в госпиталь. После выздоровления вернулся в свой полк – и снова тяжелые бои за г.Печенегу.