Родился 29 августа 1956 г. в ст. Краснодубровской Завьяловского района Алтайского края.
В 1971 г. окончил Угличское часовое училище (Ярославская обл.), в 1982 г. - Ленинградский государственный университет имени А. А. Жданова (ныне Санкт-Петербургский государственный университет) по специальности "журналистика".
В 1974-1976 гг. проходил службу в составе Группы советских войск в Германии (ГСВГ), печатался в газете ГСВГ "Советский патриот".
В 1972 г. был мастером Угличского часового завода "Чайка".
В студенческие годы был участником экологического движения "Зеленая дружина".
В 1982-1990 гг. работал журналистом, заведующим отделом Борисоглебской районной газеты "Новое время". Печатался также в газетах "Красная звезда", "Природа и человек", "Юный натуралист" и др.
Избирался народным депутатом Ярославского областного Совета.
В 1990–1993 гг. – народный депутат РСФСР, член Верховного совета РСФСР, член комитета ВС по вопросам экологии и рационального использования природных ресурсов. Во время событий сентября–октября 1993 г. выступал на стороне защитников Верховного совета.
С 1993 г. - депутат Государственной думы РФ всех восьми созывов.
12 декабря 1993 г. был избран от группы избирателей в I созыв Госдумы РФ по Рыбинскому одномандатному избирательному округу №190 (Ярославская обл.). Входил в депутатскую группу "Российский путь", был председателем подкомитета по экологическому образованию, информации и связи с общественностью думского комитета по экологии.
17 декабря 1995 г. стал депутатом II созыва Государственной думы по Рыбинскому одномандатному избирательному округу №190 от блока "Власть - народу!". Получил 32,29% голосов, второе место в округе занял кандидат, выдвинутый группой избирателей - Галина Степенко - 14,97%. В Госдуме Грешневиков был членом группы "Народовластие", секретарем комитета по экологии и председателем подкомитета по бюджетной экологической политике.
19 декабря 1999 г. избран в Госдуму III созыва по Рыбинскому избирательному округу №190 от Российского общенародного союза Сергея Бабурина (набрал 34,38%). Его ближайший соперник - Татьяна Москалькова от "Яблока" - получила 19,47%. В Госдуме входил в состав группы "Регионы России" (Союз независимых депутатов), был заместителем председателя комитета по экологии.
7 декабря 2003 г. был избран в IV созыв нижней палаты парламента от блока "Родина (народно-патриотический союз)" по Рыбинскому избирательному округу №190 (64,61%; второе место - самовыдвиженец Дмитрий Евсеев, 5,44%). Член фракции "Справедливая Россия - Родина", заместитель председателя думского комитета по экологии.
2 декабря 2007 г. стал депутатом V созыва Госдумы по списку партии "Справедливая Россия: Родина/Пенсионеры/Жизнь" (возглавлял региональную группу №81 по Ярославской обл.). Входил в партийную фракцию, комитет по аграрным вопросам.
4 декабря 2011 г. избран в Госдуму РФ VI созыва по списку партии "Справедливая Россия" (первый номер в региональной группе №65 по Ярославской обл.). Член партийной фракции, заместитель председателя комитета ГД по природным ресурсам, природопользованию и экологии.
18 сентября 2016 г. вновь избран депутатом Государственной думы VII созыва от "Справедливой России" по Ростовскому одномандатному избирательному округу №195 (Ярославская обл.). Набрал 41,88% голосов, его ближайший соперник, кандидат от партии "Родина" Владимир Денисов, - 11,99%. В Госдуме Анатолий Грешневиков вошел в состав партийной фракции. Заместитель председателя комитета ГД по экологии и охране окружающей среды.
С 2021 г. - депутат Государственной думы РФ VIII созыва от партии "Справедливая Россия – Патриоты – За правду". Был избран 19 сентября 2021 г. по Ростовскому одномандатному избирательному округу №195 (Ярославская обл.). Набрал 34,27% голосов (второе место в округе заняла Лариса Ушакова от "Единой России", 29,31%). С 12 октября 2021 г. - заместитель председателя комитета Госдумы по экологии, природным ресурсам и охране окружающей среды.
Награжден орденом Дружбы (2019), медалью ордена "За заслуги перед Отечеством" II степени (2006), орденом Святого благоверного князя Даниила Московского III степени (1999; Русская православная церковь). Имеет благодарность правительства РФ (2019).
Член Союза писателей России. Автор 16 книг, в том числе "Копье Пересвета", "Расстрелянный парламент", "Зеленый посох", "Казнь русского леса", "Информационная война", учебного пособия "Экологический букварь". Лауреат премии Союза журналистов СССР. Лауреат премий журнала "Новый мир", газеты "Сельская жизнь" и других.