Родился в Благовещенске. Окончил Нижегородскую государственную консерваторию имени М. И. Глинки и аспирантуру НГК (класс профессора Аркадия Нестерова). Участвовал в композиторских семинарах в Иванове под руководством Сергея Беринского и Василия Лобанова. С 1997 года живет в Москве. Сочинения Андрея Зеленского исполнялись в Москве (в музеях имени Глинки, Прокофьева, Музее ГУЛАГа, гостиной Юргенсона, Культурном центре ЗИЛ и др.), Нижнем Новгороде, Екатеринбурге, Иванове, а также в городах Германии и Японии. Выступает как пианист-импровизатор, а также пишет музыку для театра и кино. Заведует музыкальной частью в Московском драматическом театре АпАРТе. Член Союза композиторов России и Союза театральных деятелей.
Андрей Зеленский принимал участие в фестивалях современной музыки «Московская осень», «Другое пространство», «Творческая мастерская», «Встречи в провинции», «Полоса мокрого песка» (Нижний Новгород), в проекте «Свободный понедельник» Московского драматического театра АпАРТе. Как пианист участвовал в фестивалях «Под зонтиком Сати», «Зеркало в зеркале», «Мир гитары», «Театральное притяжение», в проектах гитариста Дмитрия Илларионова «Танцы», «Всё сложно» и «Сати-видения» (Satie`s-fiction), для которого была создана версия пьесы «Sol-weg-пульсация» для гитары, баяна, фортепиано и камерного ансамбля (исполнялась в московском Планетарии, ММДМ и Государственной Третьяковской галерее). Концерт-метаморфоза «Эсмеральда» для гитары, струнного оркестра, ударных, флейты и двух фортепиано звучал на совместном концерте фестиваля VIVACELLO и VI Международного фестиваля имени Александра Фраучи (исполнители – Дмитрий Илларионов, ансамбль Questa musica, дирижер Филипп Чижевский).
Среди сочинений: Инвенция-пастораль для трех гитар, «Метаморфозы» памяти Николая Корндорфа для камерного ансамбля, струнный квартет «На фоне одного пейзажа», Sonata al test для скрипки соло, «Соната в прелюдиях» для скрипки, голоса и фортепиано, «Маленькие радости» для голоса, саксофона, фортепиано и различных предметов, соната для альта и гитары «Крест и роза», «Пульсации» для скрипки, виолончели и баяна, «Лоскутки» для четырех флейт, Passacaglia Blu(es) для камерного ансамбля, «Ягоды» на текст Варлама Шаламова для чтеца, квартета саксофонов и фортепиано.
