Родился 4 августа 1806 г. в родовом имении Басово близ Тулы в семье исправника Тульского земского суда Петра Яковлевича Хрущёва (1763—1841) и Елены Степановны урождённой Есиповой (1770—1851). Братья и сестра Александра Петровича: Яков (1790—1809, мичман фрегата «Поллукс», погиб при кораблекрушении), Степан (1791—1865, адмирал, Архангельский военный губернатор), Николай (умер в детском возрасте), Иван (1794—1826), Борис (1795—1870, управляющий Пермской казённой палатой), Наталия (1799—1869), Василий (умер в младенчестве), Николай (1803—1828).
Выпущенный 28 апреля 1825 г. из 2-го кадетского корпуса прапорщиком в 7-й пионерный батальон, он много потрудился над своим дальнейшим образованием, посвящая всё свободное от службы время специальному изучению военного дела. В Турецкую кампанию 1828 г. Хрущёв был уже ротным командиром и принимал деятельное участие в постройке моста через р. Прут. В начале мая того же года войска наши подступили к Браилову, и 3 июня, участвуя в штурме этой крепости, Хрущёв получил 8 июля 1828 г. первую боевую награду, орден св. Анны 4-й степени с надписью «за храбрость» и 20 августа был произведён в подпоручики, а 30 августа 1829 г. за отличие в боях под Шумлой был произведён в поручики. Далее Хрущёв находился в делах при Кеприкиое, в переходе через Балканы в авангарде генерал-майора Жирова, в сражении при г. Айтос.
По окончании кампании Хрущёв, оставив строевую службу, в продолжение 17 лет подвизался на военно-педагогическом поприще, назначенный 25 мая 1831 г. воспитателем во 2-й кадетский корпус. С марта 1834 г. штабс-капитан (с 7 октября 1833 г.) Хрущёв временно был командирован в институт Корпуса горных инженеров, который в то время преобразовывался из гражданского в военное учебное заведение, для ознакомления начальства института с порядками, существовавшими в кадетских корпусах. За успешное исполнение этого поручения он был награждён бриллиантовым перстнем и произведён в капитаны (18 января 1836). В 1840 г. Хрущёв был переведён в Дворянский полк (впоследствии Константиновское военное училище), но уже в октябре того же года назначен ротным командиром в только что открытый тогда Полтавский кадетский корпус, а в июне 1843 г. командирован в Орёл для участия в организации нового, Орловского Бахтина, корпуса; но не прошло и года, как, по личному желанию великого князя Михаила Павловича, Хрущёв был переведён в 1-й Московский кадетский корпус, требовавший, благодаря неудачному составу воспитателей, усиленного надзора. 28 января 1847 г. Хрущёв был произведён в полковники.
Тяготясь в последние годы службой в корпусе, Хрущёв 4 декабря 1848 г. вышел в отставку с целью вернуться к строевой службе и в следующем году был назначен командиром Минского запасного батальона, а 18 марта 1851 г. — Волынского пехотного полка; 26 ноября того же года был награждён орденом св. Георгия 4-й степени за выслугу 25 лет в офицерских чинах (№ 8616 по списку Григоровича—Степанова). В 1853 г. полковник Хрущёв был с споим полком перевезён из Одессы в Севастополь и в апреле следующего года занял бухты южной стороны, Стрелецкую, Камышеву и Казачью и оставался на этой позиции до 2 сентября, когда присоединился к войскам, которые были сосредоточены на реке Альме. В неудачном для нас Альминском сражении Хрущёв, находившийся в резерве, с началом общего отступления занял с своим полком и двумя батареями позицию на высотах за Улукуловской долиной и, прикрывая отступление нашей армии, много содействовал тому, что оно, по признанию самих противников, было «une belle retraite».
