Cын уездного казначея в Новгороде-Северском. После окончания местной гимназии он поступил на историко-филологический факультет университета Cв. Владимира в Киеве. Студентом, Захар Коленко написал сочинение «Взгляд на город Киев», отрывок которого был напечатан в журнале «Киевская старина» (1894. — Т. XIV. — № 4. — С. 56). В журнале было также указано, что Коленко «является автором и другого сочинения, представляющего собою опыт исследования о русском языке в Галиции и заключающего в себе много ссылок на источники и литературу вопроса».
По окончании университета Коленко стал преподавать математику в Каменец-Подольской гимназии[1]; затем — в Черниговской гимназии (1838—1840)[2], откуда переведён в Иркутскую гимназию, где, несмотря на скромное положение учителя, якобы женился на дочери генерал-губернатора Энгельгардта. Возвратившись из Сибири, в 1853—1855 годах Захар Коленко был первым помощником инспектора Ришельевского лицея, затем инспектором Кишинёвской гимназии. В 1861 году он был назначен на должность директора гимназии в Херсоне. Состоял в чине действительного статского советника с 1 января 1864 года.
С 1867 года в течение шести лет он возглавлял Екатеринославскую мужскую гимназию. Затем был переведён в Елисаветград, где работал в земском высшем реальном училище. Там же, 26 октября (7 ноября) 1875 года[3], и умер от воспаления лёгких[4]. Похоронен в Кишинёве на Рышкановском кладбище у церкви Константина и Елены.