Родился 15 марта 1961 г. в Москве. Его отец - Юрий Брежнев (1933-2013), сын генерального секретаря ЦК КПСС Леонида Брежнева, в 1979-1983 гг. занимал должность первого заместителя министра внешней торговли СССР, в 1981-1986 гг. был кандидатом в члены ЦК КПСС.
В 1983 г. Андрей Брежнев окончил факультет международных экономических отношений Московского государственного института международных отношений при МИД СССР (ныне – МГИМО МИД России).
С 1983 по 1985 г. работал инженером внешнеторгового объединения "Союзхимэкспорт" Министерства внешней торговли СССР.
В 1985-1988 гг. - атташе управления международных экономических организаций Министерства иностранных дел СССР.
В 1989-1991 гг. - заместитель начальника управления внешних связей Министерства торговли СССР.
С 1991 по 1997 г. работал в различных коммерческих структурах. Также в 1996-1998 гг. возглавлял благотворительный фонд "Дети - надежда будущего".
В 1998-2001 гг. организовал и возглавил Общероссийское коммунистическое общественное движение. Выступал за национализацию приватизированной ранее госсобственности.
В июне 1999 г. заявил о желании участвовать в выборах губернатора Свердловской области, которые должны были состояться в августе того же года. Однако 28 июля избирательная комиссия региона отказала Андрею Брежневу в регистрации из-за большого количества технических ошибок в подписных листах.
19 декабря 1999 г. баллотировался на пост вице-мэра Москвы в паре с депутатом Госдумы от ЛДПР Алексеем Митрофановым. По итогам выборов они заняли пятое место из восьми, получив 0,61% голосов. Мэром Москвы был избран Юрий Лужков (69,89%).
Одновременно в качестве самовыдвиженца участвовал в выборах в Государственную думу РФ III созыва. Выдвигался по Одинцовскому одномандатному округу №110. В Думу не прошел, занял 11-е место из 19 кандидатов с результатом 2,35% голосов избирателей.
8 апреля 2001 г. баллотировался в губернаторы Тульской области от группы избирателей. Выборы проиграл: занял последнее место из четырех кандидатов, получив 1,18% голосов. Главой региона был избран Василий Стародубцев (49,09%).
В 2002-2004 гг. Андрей Брежнев был генеральным секретарем созданной им незарегистрированной Новой коммунистической партии.
В 2004-2014 гг. был членом КПРФ.
В 2014 г. избран первым секретарем центрального комитета Коммунистической партии социальной справедливости (КПСС), созданной и зарегистрированной в 2012 г. политтехнологом Андреем Богдановым.
В 2014 г. безуспешно баллотировался от КПСС в Симферопольский, Брянский, Ялтинский, Бахчисарайский городские советы депутатов. Также выдвигался от КПСС в Государственное собрание Республики Марий Эл VI созыва, Законодательную думу Хабаровского края VI созыва, Собрание депутатов Ненецкого автономного округа XXVII созыва, Государственный совет Республики Татарстан V созыва, Государственный совет Республики Крым I созыва, Брянскую областную Думу VI созыва. Ни в одно из законодательных собраний избран не был.
В 2015 г. вновь баллотировался от КПСС в Костромскую областную Думу VI созыва, Законодательное собрание Калужской области VI созыва, Законодательное собрание Новосибирской области VI созыва. Избран не был.
С 2015 г. являлся владельцем и заместителем генерального директора компании "Южная Ривьера плюс" (г. Алушта, Республика Крым), специализирующейся на организации водоснабжения и строительстве.
С 2016 г. был владельцем и генеральным директором торговых фирм "Риэлткомп" и "Галинекс" (Москва).
В 2016 г. вступил в партию "Родина", возглавил ее региональное отделение в Республике Крым.
18 сентября 2016 г. участвовал в выборах в Государственную думу РФ VII созыва от партии "Родина". Баллотировался по единому федеральному округу в составе партийного списка кандидатов (четвертый номер в региональной группе №1, Республика Крым и Севастополь), а также по Севастопольскому одномандатному округу №219. В Думу не прошел. Список "Родины" не преодолел 5-процентный проходной барьер, набрав 1,51% (восьмое место из 14). В одномандатном округе Андрей Брежнев занял шестое место из девяти с результатом 1,94% голосов.
10 сентября 2017 г. участвовал в выборах в Совет депутатов муниципального округа "Дорогомилово" в Москве по многомандатному округу №3. В Совет депутатов не прошел, заняв шестое место из 13 кандидатов.
10 июля 2018 г. скончался в Крыму от инфаркта.
Был дважды женат. Имел двух сыновей.