Родился 25 октября 1950 года в деревне Гоношиха Алтайского края. Закончил среднюю школу в городе Заринске. Служил на флоте, работал на стройках Дальнего Востока, был моряком и кочегаром. В 1974 поступил на заочное отделение Литературного института им. А.М. Горького, но не окончил его. В 1974 году перебрался в Москву. В середине восьмидесятых он вместе с поэтами Алексеем Парщиковым и Иваном Ждановым создал неформальную литературную группу «метафористов».
Его стихи: «Горизонтальная страна...», «Печатными буквами пишут доносы...» и «Сгорая, спирт похож на пионерку...» — были опубликованы в апреле 1987 года в журнале «Юность» в рубрике «Испытательный стенд».
В браке с Натальей Лясковской рождён сын Марк.
В браке с Галиной Рыбаковой рождены два сына — Рыбаковы Егор и Андрей.
В последние годы А. Ерёменко редко публикует новые тексты. В 2002 году он был удостоен премии имени Бориса Пастернака.
Литературный критик Кирилл Ковальджи отметил: „Гандлевский, Еременко, Арабов, Друк в той или иной мере прибегают к «антипоэзии»“.