Андрей был против третьего замужества матери. О. С. Павлищева пишет по этому поводу мужу 12 сентября 1835 года: «Полье… выходит наконец замуж за итальянца – не графа, но очень богатого, Бутера; она принимает поздравления. Ее сын… так этим удручен, что уехал на Кавказ и поступил в армию». Впрочем, существует предположение, что Шувалов отправился туда не добровольно, а был сослан Николаем I за какую-то неизвестную провинность.
Юный граф начинает службу подпрапорщиком в Грузинском гренадерском полку, но в том же 1835 году его переводят юнкером в Нижегородский драгунский полк. Он участвует в боевых действиях против горцев, получает ранение и награждается знаком отличия Военного ордена[22]. Спустя два года, опять же за отличие, Шувалова производят в первый офицерский чин прапорщика, а в 1838-м он прикомандировывается к лейб-гвардии Гусарскому полку и прибывает в Петербург с солдатским Георгием в петлице, окруженный романтическим ореолом воина, пролившего кровь на поле брани.
Еще на Кавказе происходит его знакомство со служившим в том же полку М. Ю. Лермонтовым, придавшим, по мнению современников, Печорину некоторые черты характера и даже портретное сходство с Андреем Шуваловым. В столице они вновь оказываются однополчанами, вместе посещают салон Карамзиных, а кроме того, входят в так называемый «кружок шестнадцати». О последнем до сих пор известно далеко не все.
Один из его участников позднее вспоминал: «В 1839 году в Петербурге существовало общество молодых людей, которое назвали, по числу его членов, кружком шестнадцати. Это общество составилось частью из окончивших университет, частью из кавказских офицеров. Каждую ночь, возвращаясь из театра или бала, они собирались то у одного, то у другого. Там, после скромного ужина, куря свои сигары, они рассказывали друг другу о событиях дня, болтали обо всем… с полнейшей непринужденностью и свободой, как будто бы III отделения… вовсе и не существовало; до того они были уверены в скромности всех членов общества».
И поныне мы не знаем поименно всех участников этого собрания, но было оно довольно разношерстным, и говорить о какой-либо его политической направленности нет оснований. Тем не менее семена либерализма будущего земского деятеля, по всей вероятности, проросли именно в ту пору.
Вскоре жизненные пути бывших товарищей разошлись: Лермонтов отправляется в повторную ссылку на Кавказ, а Шувалов назначается адъютантом к фельдмаршалу И. Ф. Паскевичу. В 1842 году Андрей Павлович «за раною» выходит в отставку, уезжает за границу и через два года женится на дочери графа М. С. Воронцова, Софье (настоящим ее отцом, по весьма правдоподобной гипотезе, был Пушкин).
В 1848 году возобновляется служба А. П. Шувалова при князе Паскевиче, но в скором времени он назначается флигель-адъютантом, а затем переводится штаб-ротмистром в Кавалергардский полк, где в течение нескольких лет несет строевую службу. По завершении «искуса», в 1854 году, сохранив лишь должность флигель-адъютанта, граф покупает участок на Моховой и приступает к постройке собственного дома, намереваясь покинуть материнский особняк на Английской набережной, где он жил до сих пор. К тому времени Андрей Павлович был уже отцом четверых детей; в 1856 году родилась его младшая, и последняя, дочь Мария.
С воцарением Александра II для России началась новая эпоха. Она пробудила к незнакомой дотоле общественной жизни многих людей, почувствовавших себя не просто «подданными», но еще и гражданами. Не последнее место среди них занимал граф А. П. Шувалов. Он активно включился в работу, связанную с подготовкой крестьянской реформы, и в 1861 году удостоился «монаршего благоволения» «за отличное исполнение высочайше возложенного поручения». В 1865 году Шувалов выходит в отставку «по домашним обстоятельствам», но, вероятнее всего, им руководило желание развязать себе руки.
С самого начала возникновения земских учреждений он всецело отдался этому делу. Широко образованный, с твердыми убеждениями и инициативой, А. П. Шувалов энергично отстаивал независимость городского самоуправления. На одном из ноябрьских заседаний земского собрания в том же 1865 году граф произнес речь, в которой были такие слова: «Я убежден вполне, что с того дня, как открылось в России первое земское собрание, началась борьба с местным административным произволом, – борьба беспощадная, борьба окончательная. Я не сомневаюсь также, что каждое наше слово, каждое наше дело должно стремиться к уничтожению этого произвола».
Возможно, современный человек не усмотрит в них ничего особенного и даже воспримет как должное, но в ту пору они звучали почти революционно. 11 декабря 1865 года тогдашний министр внутренних дел П. А. Валуев отмечает в своем дневнике: «Князь Горчаков… говорит про графа Андрея Павловича Шувалова, что он пренебрег мнением общества. На него многие смотрят, как на агитатора, решившегося идти далеко».