Алексей Кузьмич Стерелюхин родился 30 марта 1913 года в селе Тоцкое ныне Тоцкого района Оренбургской области в семье крестьянина. Русский. Член ВКП(б) с 1935 года. Образование неполное высшее, окончил педучилище в Бузулуке. До призыва на военную службу работал пропагандистом в Тоцком райкоме партии и одновременно окончил два курса Оренбургского пединститута.
В Красной Армии с 1942 года. В действующей армии с июля 1943 года.
Окончил Рузаевскую военную школу подготовки офицеров. В боях Великой Отечественной войны с июля 1943 года до дня гибели — 29 октября 1943 года, воевал на Центральном фронте, участвовал в Курской битве, освобождении Украины. Тяжело ранен. Награждён орденом Красной Звезды.
23 сентября 1943 года 2-й батальон 207-го гвардейского стрелкового полка 70-й гвардейской стрелковой дивизии первым в полку форсировал Днепр у села Теремцы, а затем Припять южнее города Чернобыль Киевской области. Парторг батальона Стерелюхин руководил переправой и, достав лодку, лично перевёз бойцов и вооружение. Парторг сумел сплотить солдат на отражение всех контратак фашистов.
В момент, когда на исходе были боеприпасы, а на позиции батальона гитлеровцы бросили двенадцать танков и крупные силы пехоты, Стерелюхин первым поднялся в контратаку. С возгласом «Гвардейцы, вперёд за Родину!» он с противотанковыми гранатами бросился навстречу врагу. Воодушевленные примером бесстрашия своего парторга, бойцы дружно пошли вперёд. Фашисты, не устояв против натиска гвардейцев, откатились назад, потеряв четыре танка и десятки солдат и офицеров. Десять гитлеровцев сразил сам А. К. Стерелюхин. Во время боя отважный парторг был ранен и 29 октября 1943 года от полученных ранений скончался в госпитале.
Указом Президиума Верховного Совета СССР «О присвоении звания Героя Советского Союза генералам, офицерскому, сержантскому и рядовому составу Красной Армии» от 15 января 1944 года за «образцовое выполнение боевых заданий командования по форсированию реки Днепр и проявленные при этом мужество и героизм» Стерелюхину Алексею Кузьмичу было присвоено звание Героя Советского Союза с вручением ордена Ленина и медали «Золотая Звезда».
Похоронен в городе Льгов Курской области.
