Родился в семье шахтёра. Был младшим в семье — рос с тремя старшими братьями и сестрой. Школьником участвовал в художественной самодеятельности, выступал в «красных уголках», а после школы работал монтировщиком в Донецком ТЮЗе, где по-настоящему «заболел» сценой.
Служил в рядах Советской Армии (войска связи на территории Германской Демократической Республики), работал проводником поезда.

В 1973 году поступил в Горьковское театральное училище, обучался у тех же педагогов, которые в свое время учили таких мастеров сцены и экрана, как Евгений Евстигнеев, Людмила Хитяева и других.

- В 1977 году главный режиссер Пензенского театра С.М.Рейнгольд пригласил Зеленченко-выпускника в Пензу, пообещав, как рассказывает Олег Трофимович, «роль Лермонтова, оклад 85 рублей и комнату в общежитии». С тех пор вся жизнь актера связана с пензенским театром.
- С 1985 по 2008 год включительно и с 2010 по 2011 год Олег Трофимович занимал пост заведующего труппой пензенского областного драматического театра имени А.В. Луначарского. Более 20 лет игру на сцене он совмещал с этой нелегкой работой, которую сам часто сравнивал с работой авиадиспетчера, «когда самолёт на взлетной полосе».
По мнению О.Зеленченко, «театр — это семья, и руководить им нужно, как семьей».
- Сейчас продолжает играть на сцене как актер.

В 1998 году О. Т. Зеленченко было присвоено почётное звание заслуженного артиста России.

Олег Трофимович женат с 1979 года, у него взрослая дочь. И жена, и дочь по профессии — юристы.

Среди литературных пристрастий Олега Зеленченко на первом месте — проза Чехова.

«С ним приятно работать в спектакле,– говорил о нём заслуженный артист РСФСР И. В. Эрельт,– к нему можно в любое время обратиться по любому вопросу, зайти в кабинет, позвонить домой…».

Народная артистка России М. И. Тамбулатова вспоминает их совместную работу в спектакле по пьесе В. С. Розова «Гнездо глухаря»: «Олег играл потерявшегося, несчастливого мальчишку Прова, а я – его мать. Огромные, полные беды глаза так действовали на меня, что я чувствовала его боль, как боль родного сына и рыдала по настоящему».

Народная артистка России Л. А. Лозицкая рассказывает о спектакле «Лисички» Л. Хелман: «Однажды в Ростове на гастролях я на свой страх и риск чуть изменила текст, чтобы придать сцене новую окраску. Мгновение – и Олег понял мой замысел, включился в игру! Так важно, чтобы партнёры были отзывчивы на экспромты!»

Из музыки он предпочитает ретро, джаз, блюз «и другую хорошую музыку».

1. http://www.penzateatr.ru/people/zelenchenko

Роли, сыгранные за четверть века, подтвердили его широкий жанровый диапазон, не вписывающийся в рамки одного амплуа. И все же его острая характерность чаще всего выводит О.Т. Зеленченко на роли злодеев, обманщиков, ябед, яркую галерею которых он создал в Пензе. В репертуарном листе артиста более 80 ролей, в их числе: «Бешеные деньги» А. Н. Островского, «Дама невидимка» П. Кальдерона, «Милый друг» по Ги де Мопассану, «Берег» Ю. В. Бондарева, «Деньги для Марии» В. Г. Распутина, «Иван Васильевич по М. А. Булгакову.

Сегодня играет в спектаклях:
1. Куклы (В.Белякович) — Дон Лусио
2. Люкс № 13 (Р.Куни) — Официант
3. Плутни Скапена (Ж.-Б.Мольер) — Аргант
4. Поминальная молитва (Г.Горин) — Ребе
5. Ревизор (Н.Гоголь) — Петр Иванович Добчинский