Шестов взял под свою защиту все тягловое городское общество: «Ни один московский купец и мещанин, взятый в полицию, не может быть окончательно обвинен или оправдан без приговора общества и его головы». Именно на борьбу с самоуправством полиции уходили основные силы и отвага Шестова. Боролся он и с казнокрадством в городском хозяйстве, в чем заручился поддержкой генерал-губернатора князя Д. В. Голицына, благоволившего к «дедушке Андрею», как звали своего городского голову московские обыватели.
В 1862 году было введено новое «Положение городского устройства Москвы». Установлены пять сословий (потомственные дворяне, личные дворяне, купцы, мещане и ремесленники), управление каждого из которых возлагалось на свою сословную Управу. Для ведения же общегородских учредили Общую думу, куда каждое сословие через сто человек своих выборных избирало из своей среды 35 гласных. Из состава Общей думы, которая занималась составлением законов (приговоров) избиралась Распорядительная Дума для внедрения этих законов в жизнь (позже переименована в Городскую управу). Сословных старшин, их товарищей, городского секретаря, членов Распорядительной думы, казначеев утверждал в их должностях московский генерал-губернатор. На должность городского головы, председательствовавшего как в Общей думе, так и в Распорядительной думе, в 1860-х годах требовалось избирать не менее двух лиц, окончательный же выбор из них оставался за генерал-губернатором. Первые выборы Общей думы состоялись в 1863 году.
В Шестигласной думе заседало, главным образом, купечество. Теперь же она стала всесословной. Выборы городского головы состоялись 16 марта 1863 гола в большом зале Российского Благородного собрания. Все хоры были заполнены зрителями. Из шести претендентов на должность городского головы И. Ф. Мамонтов снял свою кандидатуру. Первый баллотировался И. А. Лямин. За него было опущено 199 избирательных шаров и 262 неизбирательных. Следующий – Г. И. Хлудов («за» – 278, «против» – 183), князь А. А. Щербатов («за» – 338, «против» – 123), А. И. Кошелев («за» – 156, «против» – 305), И. В. Селиванов («за» – 82, «против» – 379). Гвардии поручик князь Александр Алексеевич Щербатов был утвержден генерал-губернатором как председатель новой Думы, основанной на началах истинного самоуправления и всесословности.