Родился 4 июля 1958 г. в г. Энгельсе Саратовской области.
В 1980 г. окончил Саратовский политехнический институт (ныне Саратовский государственный технический университет им. Ю. А. Гагарина) по специальности "производство строительных изделий и конструкций" (квалификация "инженер-строитель-технолог"), в 2005 г. Саратовскую государственную академию права (ныне Саратовская государственная юридическая академия) по специальности "юриспруденция".
Кандидат экономических наук. В 2006 г. в Саратовском государственном социально-экономическом университете защитил диссертацию на тему "Совершенствование государственного управления качеством и конкурентоспособностью продукции российских предприятий".
С 1980 г. работал инженером отдела стекловарения Всесоюзного научно-исследовательского института технического и специального строительного стекла.
С 1981 по 1998 г. - сварщик, прораб, главный инженер управления "Сароблсельстрой", строительно-монтажных управлений (СМУ) треста "Энгельсхимстрой", начальник СМУ "Энгельсхимстрой" и "Энгельсстрой", главный инженер треста "Энгельсстрой".
В 1998-2000 гг. - первый заместитель министра жилищно-коммунального хозяйства Саратовской области, заместитель министра жилищно-коммунального хозяйства по капитальному строительству.
С 2000 по 2001 г. являлся главным инженером ЗАО "Трест "Энгельсстрой".
В 2001-2005 гг. - заместитель главы Энгельсского муниципального образования по промышленности, энергетике, транспорту и связи.
С 2005 по 2006 г. исполнял обязанности главы Марксовского муниципального образования.
В 2006 г. занял должность министра экономического развития и торговли Саратовской области.
В октябре 2007 г. был назначен и. о. заместителя председателя правительства Саратовской области. 31 октября того же года утвержден на посту заместителя председателя правительства региона.
С марта 2012 г. по май 2014 гг. - генеральный директор ЗАО "Балаково – Центролит".
В 2012-2016 гг. - депутат Саратовской областной думы V созыва. Был избран 14 октября 2012 г. по Балаковскому одномандатному избирательному округу №21 (баллотировался от партии "Единая Россия"). За него проголосовали 62,65% избирателей. Второе место заняла кандидат от КПРФ Анна Цыганова (16,92%).
С мая по декабрь 2014 г. занимал должность генерального директора ЗАО "Энгельсский локомотивный завод".
В 2014-2016 гг. - генеральный директор ООО "Первая локомотивная компания".
В сентябре 2016 г. занял должность первого заместителя председателя правительства Саратовской области.
20 июля 2017 г. депутаты Собрания депутатов Энгельсского муниципального района Саратовской области единогласно избрали Александра Стрелюхина главой района. Ранее его кандидатура была предложена конкурсной комиссией.
В июне 2019 г. был назначен вице-губернатором-председателем правительства Саратовской области.
В конце 2020 г. возглавил дирекцию Государственного казенного учреждения "Центр развития Саратовской агломерации".
С 2021 г. - депутат Государственной думы РФ VIII созыва от "Единой России". Был избран 19 сентября 2021 г. по Энгельсскому одномандатному избирательному округу №166 (Саратовская обл.). Набрал 51,63% голосов (второе место в округе заняла депутат Госдумы РФ VII созыва от КПРФ Ольга Алимова; 22,99%).
Награжден медалью ордена "За заслуги перед Отечеством" II степени.