Родился 13 сентября 1915 года в городе Кургане в семье рабочего. Русский.
Окончил 7 классов неполной средней школы, в 1935 году – Курганское железнодорожное училище. Работал помощником машиниста паровоза на станции Завитая и машинистом паровоза на станции Татарская Омской железной дороги.
В армию призван в 1942 году Татарским райвоенкоматом Новосибирской области. По окончании полковой школы в марте 1942 года отправлен на фронт. Воевал в составе войск Сталинградского, Южного и 3-го Белорусского фронтов. Был ранен. Член ВКП(б)/КПСС с 1943.
Командир орудия 358-го артполка (126-я стрелковая дивизия, 43-я армия, 3-й Белорусский фронт) старшина Черемухин особо отличился 6–9 апреля 1945 года на подступах и при штурме Кенигсберга (ныне Калининград). Расчет 76-мм орудия Черемухина действовал смело и решительно.
В этих боях расчет сибиряка метким артиллерийским огнем уничтожил три и подавил четыре пулемета, заставил замолчать минометную батарею, поджег две автомашины с боеприпасами.
Еще большего успеха достиг Александр Черемухин в боях в самом Кенигсберге, где гитлеровцы каждый дом превратили в крепость, старшина уничтожил пять пулеметных точек, установленных в зданиях, два артиллерийских орудия и около 25 солдат, взорвал два склада с боеприпасами, подавил огонь артиллерийской батарей противника. В бою за Кенигсбергский зоопарк прямой наводкой – тринадцать пулеметов вместе с их расчетами.
В апрельских боях 1945 года был вторично (на сей раз тяжело) ранен, в силу чего с мая 1945 по март 1946 года находился на излечении в госпиталях.
Звания Героя Советского Союза был удостоен на основании Указа Президиума Верховного Совета СССР от 19 апреля 1945 года.
После демобилизации работал в Новосибирской области в депо станции Татарская, а в 1950 году вернулся на родину в Курган, где трудился в тресте «Курганстрой» – комендантом общежития, а в артели «Новый быт» – наладчиком оборудования. Затем служил в органах МВД.
С 1954 года – пенсионер.
Награжден орденами Ленина, Отечественной войны 1-й и 2-й степени, Славы 2-й и 3-й степени, многими медалями.
Скончался 31 декабря 1987 года. Похоронен в городе Кургане.
Имя Героя Советского Союза А.Е. Черемухина увековечено на памятной мемориальной доске, установленной на территории Калининградского зоопарка. В Новосибирске его имя увековечено на Аллее Героев у Монумента Славы [179, 217, 240, 256, 417, 549893, 1200].