Владимир Алексеевич Лещенко родился в 1959 году. В 1984 году окончил Алтайский государственный медицинский институт, в 1999 году окончил юридический факультет Алтайского государственного 
университета, в 2009 году Всероссийский заочный финансово-экономический институт, получив специальность «экономист».
Начинал свою профессиональную деятельность с должности хирурга Первой горбольницы Барнаула (1984–1987 годы). С 1987 по 2001 год работал главным врачом ЦРБ Смоленского района, руководил Станцией переливания крови города Бийска (2001–2002 годы). С 2002 по 2016 год являлся главным врачом Алтайского диагностического центра, работал заместителем председателя комитета по здравоохранению и науке Алтайского краевого Законодательного Собрания, секретарем Медицинской палаты Алтайского края. Член Правления общественной организации Красный Крест, член правления Ассоциации диагностических центров России и стран СНГ, депутат Алтайского краевого Законодательного Собрания трех созывов.
Кроме того, занимал должности директора Барнаульского медицинского колледжа, председателя Совета директоров медицинских колледжей и техникума Алтайского края.
С 2009 года – кандидат медицинских наук. Тема диссертации: «Заболеваемость населения, проживающего в районах ракетно-космической деятельности, и разработка комплекса профилактических медико-социальных мероприятий».
В 2008 году В.А. Лещенко присвоено звание «Заслуженный работник здравоохранения Российской Федерации». В 2009 году он награжден медалью Алтайского края «За заслуги в труде», с 2013 года – Почетный гражданин Петропавловского района.
На новом посту Владимир Лещенко сменил Сергея Коваленко, который назначен главным врачом Майминской районной больницы.