Родился 4 октября 1892 г. (22 сентября по старому стилю 1892 г.) в деревне Большая Александровка Санкт-Петербургской губернии Российской империи (ныне Ленинградская обл. РФ). Дата рождения была уточнена в 2021 г. по метрической книге исследователями Минобороны РФ, ранее днем рождения военачальника считалось 30 сентября (18 сентября по ст. ст.) - эта дата выбита на захоронении военачальника в Кремлевской стене.
После окончания начальной земской школы в 1903 г. Андрей Хрулев работал подмастерьем золотых дел мастера в Санкт-Петербурге. Затем посещал вечерние общеобразовательные курсы, а в 1911 г. завершил учебу в вечерней школе казенных десятников. В 1912 г. был арестован за революционную деятельность и после шестимесячного заключения на два года выслан из города.
В 1915-1917 гг. работал счетоводом на Охтинском пороховом заводе в Петрограде (в 1924-1991 гг. - Ленинград, ныне Санкт-Петербург), был секретарем заводского комитета, членом Пороховского районного совета. В дни Февральской революции 1917 г. вступил в красногвардейский отряд, а с марта того же года - в РКП(б). Участвовал в захвате Зимнего дворца в ходе Октябрьской революции, в подавлении вооруженного выступления Керенского – Краснова, выполнял агитационную работу в Могилевской губернии. По возвращении в Петроград был избран членом Пороховского районного комитета большевистской партии, заместителем председателя районного Совета рабочих и солдатских депутатов, затем назначен комендантом революционной охраны и членом чрезвычайной политической тройки Пороховского района.
В августе 1918 г. Андрей Хрулев добровольцем вступил в ряды Рабоче-крестьянской Красной армии (РККА), был зачислен в 1-й советский полк в Петрограде. В период Гражданской войны 1917-1922 гг. сражался против войск генерала Антона Деникина на юге страны, принимал участие в разгроме сил генерала Петра Врангеля, сражался с вооруженными формированиями Нестора Махно на Украине. Занимал должность помощника начальника, а затем начальника политотдела 11-й кавалерийской дивизии 1-й Конной армии.
После войны проходил службу в должностях начальника политотдела и военкома 14-й кавалерийской дивизии Северо-Кавказского военного округа (ВО), военкома 4-й кавалерийской дивизии, командира и комиссара 44-го территориального кавалерийского полка 3-й кавбригады.
В 1925 г. окончил Военно-политические академические курсы высшего политсостава РККА в Москве и занял должность военного комиссара - начальника политического отдела 10-й кавалерийской дивизии Московского ВО. В 1928 г. стал заместителем начальника политического управления этого округа.
В июле 1930 г. решением Реввоенсовета СССР Андрей Хрулев был назначен начальником Центрального военно-финансового управления РККА по военным и морским делам. В 1934 г. стал начальником Финансового управления Народного комиссариата обороны (НКО) СССР. В 1936 г. в звании корпусного комиссара получил назначение на должность начальника Управления делами НКО СССР. В том же году возглавил Строительно-квартирное управление НКО СССР, а в 1938 г. - Управление военного строительства Киевского особого ВО.
В октябре 1939 г. Андрей Хрулев приказом народного комиссара обороны Климента Ворошилова был назначен начальником только что созданного Управления снабжения РККА. В ходе Советско-финляндской войны 1939-1940 гг. по инициативе Хрулева оно было реорганизовано в Главное интендантское управление РККА под его руководством.
В начале Великой Отечественной войны 1941-1945 гг. генерал-лейтенант интендантской службы Андрей Хрулев был назначен заместителем наркома обороны СССР, а с 1 августа 1941 г. одновременно с этим являлся начальником Тыла Красной армии и по совместительству начальником Главного управления тыла (до его упразднения в 1943 г.). В 1942-1943 гг. исполнял также обязанности народного комиссара путей сообщения.
Под его руководством органы тыла РККА выполняли сложные и ответственные задания в годы войны, в частности, обеспечивали войска всем необходимым в ходе Московской битвы 1941-1942 гг. Осенью 1941 г. на Ладожском озере начала действовать ледовая трасса - Дорога жизни, сыгравшая в дальнейшем главную роль в снабжении Ленинграда и Ленинградского фронта. В 1942 г. для подачи горючего осажденному городу по дну Ладожского озера был проложен 35-километровый трубопровод. По инициативе Андрея Хрулева был построен ряд железнодорожных линий, в т. ч. Кизляр – Астрахань, которые сыграли решающую роль для достижения победы в Сталинградской битве 1942-1943 гг. Всесторонняя подготовка тыла к войне с Японией в 1945 г. и успешная его работа по обеспечению боевых действий советских войск в ходе кампании против Квантунской армии явились одним из важнейших условий ее разгрома.
После войны генерал армии Андрей Хрулев продолжал руководить тыловыми структурами Советской армии. С марта 1946 г. занимал должность начальника Тыла Вооруженных сил (ВС) - заместителя министра ВС СССР по тылу (с 1950 г. - заместителя военного министра).
С 1951 г. занимал руководящие посты на гражданской службе (в запас был уволен в октябре 1953 г.): являлся заместителем министра промышленности стройматериалов СССР (1951–1953), заместителем министра автомобильного транспорта и шоссейных дорог СССР (1953–1956), заместителем министра строительства СССР (1956–1958).
В апреле 1958 г. был возвращен в кадры ВС и зачислен в Группу генеральных инспекторов Министерства обороны СССР.
Андрей Хрулев скончался в Москве 9 июня 1962 г. на 70-м году жизни. Урна с прахом замурована в Кремлевской стене на Красной площади столицы.
В 1946-1950 гг. - депутат Верховного Совета СССР.
Генерал армии (1943).
Был награжден двумя орденами Ленина (1940, 1945), четырьмя орденами Красного Знамени (1923, 1930, 1944, 1947), двумя орденами Суворова I-й степени (1943, 1944), медалями, а также иностранными наградами.
Автор публикаций по вопросам организации тыла и материально-технического обеспечения, а также мемуаров, которые печатал в виде статей (в 2017 г. рукопись его мемуаров была издана ограниченным тиражом в виде книги "Записки интенданта").