Родился Александр Павлович Лебедев 18 ноября 1918 года в Анжеро-Судженске (по другим источникам, в Мариинске) Кемеровской области. Окончил неполную среднюю школу, работал на золотых приисках. В 1939 году Александр Павлович с семьей переехал в город Сталинск (Новокузнецк), здесь окончил курсы младших лейтенантов.
Боевой путь начал в мае 1942-го, успешно освоил снайперское дело - помогли уроки деда, сибирского охотника. А потом начал учить меткой стрельбе и других бойцов, стал зачинателем и организатором снайперского движения в своём полку.
Воевал на Брянском, Западном, Центральном фронтах. Стал зачинателем снайперского движения в 1-м батальоне 105-й стрелковой бригады. Младший лейтенант, комсорг 1287-го стрелкового полка 110-й стрелковой дивизии 61-й армии Брянского фронта, Александр Павлович Лебедев меньше чем за год, с октября 1942 по июнь 1943 года, уничтожил 307 фашистов. Немногие снайперы в Красной Армии в годы Великой Отечественной войны могли похвастаться таким количеством убитых фашистских солдат и офицеров. За эти подвиги 10 июня 1943 года был представлен к высшей награде страны - званию Героя Советского Союза. В наградном листе на звание Героя Советского Союза об Александре Лебедеве говорится: «Проявляя исключительный героизм, военную смекалку, умение и настойчивость, истребил лично с октября 1942 по 23 мая 1943 года 307 фашистских солдат и офицеров. Являясь отличным снайпером, обучил снайперскому искусству 45 человек, лучшие из которых имели на своем счету большое количество убитых врагов. Всего Лебедев со своими учениками уничтожил 1120 солдат и офицеров врага».
«Там, где появлялся Лебедев, немцы не могли ходить во весь рост. Он заставлял их ползать, как пресмыкающихся...», - говорила о нём фронтовая газета. Возможно, эти строчки принадлежат перу корреспондента газеты
Брянского фронта «На разгром врага!». 
К июню 1943 года младший лейтенант Александр Лебедев был ответственным секретарём бюро комсомола 1287-го стрелкового полка 110-й стрелковой дивизии 61-й армии Брянского фронта. В июне 1943 года подготовил очередную группу - 29 снайперов.
Представление на высокое звание еще ходило по инстанциям, а Александр Лебедев успел отличиться в сражении на Курской дуге. Когда наши войска перешли в наступление, он сменил снайперскую винтовку на автомат и ходил в рукопашную в передовых подразделениях полка. Сибиряк был не только снайпером, но и разведчиком, не раз пробирался в тыл врага и приводил «языков».
14 августа 1943 года в бою за деревню Одрино был тяжело ранен командир роты, бойцы залегли под кинжальным огнём двух пулемётов. Выполнение боевой задачи могло быть сорвано. Младший лейтенант А. П. Лебедев принял командование на себя. Из снайперской винтовки снял пулемётчиков и личным примером поднял солдат в атаку. Стремительным броском бойцы ворвались в деревню и стали очищать дома от фашистов. В конце боя отважный комсорг был смертельно ранен осколком снаряда.
Похоронен в деревне Одрино Карачаевского района Брянской области.
Согласно некоторым источникам, к моменту гибели А. П. Лебедев уничтожил ещё около 40 фашистов (официальных документов, подтверждающих это, не имеется).
Указом Президиума Верховного Совета СССР от 4 июня 1944 года за «образцовое выполнение боевых заданий командования на фронте борьбы с немецкими захватчиками и проявленные при этом мужество и героизм» младший лейтенант Александр Лебедев посмертно был удостоен высокого звания Героя Советского Союза. Был награждён орденами Ленина и Золотая звезда (04.06.1944), Красной Звезды (25.05.1943) и медалью «За отвагу» (23.12.1942).