Лещинський закінчив грати в 24 роки і став працювати тренером в севастопольській ДЮСШОР № 5. Пізніше працював муляром, сторожем, менеджером, завідувачем прокатом автомобілів, слюсарем, шкільним учителем. У 1999 році повернувся в ДЮСШОР, через 1,5 року перейшов до новоствореного ФК «Севастополь», в якому став асистентом у Валерія Петрова. Був у команді також старшим тренером другої команди, чотири рази — виконуючим обов'язки головного тренера, головним тренером, спортивним директором. У 2010 році вивів команду в Прем'єр-лігу чемпіонату України.
У 2012-2013 був головним тренером клубу «Титан» (Армянськ). У початку 2014 перейшов до російського клубу ПФЛ «Тосно», 4 березня став головним тренером[1]. 15 травня 2014 року через конфлікт з гравцями був відправлений у відставку[2].
У серпні 2014 очолив фейковий «СКЧФ Севастополь-2», який виступає в так званому чемпіонаті Криму[3]. Після того, як у головного тренера основної команди Сергія Дієва стався інсульт, очолив основну команду. Після закінчення дебютного чемпіонату так званої Кримської прем'єр-ліги, в якому СКЧФ зайняв 2 місце, «керівництво» клубу вирішило не продовжувати контракт з тренером.
З серпня 2016 був головним тренером грузинського клубу «Гурія» (Ланчхуті).