В Москве Алексея Ивановича долго не задержали. Предложили поехать военным атташе в Алжир. По тем временам не самая спокойная должность. Еще не закончилось бурное десятилетие 1960-х годов, когда эта страна пережила многочисленные потрясения – войну, борьбу за независимость, Эвианское соглашение 1962 года, референдум и, наконец, долгожданную свободу, а вместе с ней и массу проблем. Одна из которых – многочисленные минные поля на границе с Марокко и Тунисом. Своими силами алжирцы справиться с таким количеством мин не могли. Они обратились за помощью к Западной Германии, Италии, Швеции, но им отказали. Советский Союз согласился оказать помощь в уничтожении минно-взрывных заграждений. Туда прибыла одна оперативная группа советских инженерных войск, потом вторая. За три года советские саперы обезвредили 1,5 млн мин, разминировали 800 км минно-взрывных полос, очистили 120 тыс. гектаров земли.
Потом приехали советские советники и специалисты, которые помогали создавать национальную армию страны.
Так что у Алексея Ивановича Лебедева в Алжире хватало забот. Однако, как говорят, пути Господни неисповедимы. Он был неожиданно вызван в Москву и получил новое назначение – военным атташе в Париж.
По возвращении из Франции генерал-майор Лебедев возглавил факультет в Военно-дипломатической академии. Несколько лет преподавал опыт молодым, а в 1975 году был назначен военным атташе в Берлин, в Германскую Демократическую Республику.
По возвращении из ГДР уволился в запас.
…Помнится несколько лет назад генерал-майор Владимир Стрельбицкий, друг и однокашник по академии, сказал о Лебедеве прекрасные слова. Я записал их на диктофон. Этими словами и хочу закончить свой рассказ о воздушном асе, Герое, выдающемся разведчике.