Родился в с. Маховица Орловской губернии в крестьянской семье.

Учился в Маховицкой сельской школе, а в летнее время работал пастухом по найму.

В 1920 г. семья Малехоньковых переехала в Шарлыкскую волость Оренбургской губернии, где Григорий Андреевич до 1921 г. работал пастухом. В 1921-1923 гг. работал рассыльным Шарлыкского волостного земельного отдела, в 1923-1924 гг. – ответственным секретарем Шарлыкского волкома комсомола.

В 1924-1927 гг.Г.А. Малехоньков учился в Оренбургском сельскохозяйственном техникуме и по его окончании был направлен в ОГПУ г. Тарткуль Кара-Калпакской АССР, где работал до 1929 г. помощником уполномоченного, уполномоченным, а затем старшим уполномоченным. В 1929–1931 гг. Малехоньков работал инспектором контрольной комиссии Рабоче-Kрестьянской инспекции г. Кзыл-Орда Казахской ССР, с 1931
по 1932 гг. – заместителем директора, затем директором Бурлинской МТС Бурлинского района 3ападно-Казахстанской области.

В 1932 г. Г.А. Малехоньков возвратился в Оренбургский округ и до 1936 г. работал директором Соболевской МТС Тепловского района. В 1936–1938 гг. работал начальником зернового управпения Оренбургского (с 1938 г. Чкаловского) областного земельного отдела и сельхозснаба. С 1938 г. на руководящей партийной работе в Чкаловской (Оренбургской) обл.

Член Компартии с 1927.

Окончил Высшую Партийную школу при ЦК КПСС (1952-55).

С 1 августа 1941 (постановлением ГКО) - уполномоченный ГКО СССР на заводе, изготовляющем боеприпасы.
В 1944-48 - 3-й секретарь Куйбышевского обкома ВКП(б).
В 1948-51 - пред. Куйбышевского облисполкома.
В мае 1951-июле 1952 - 1-й секретарь Смоленского обкома партии.
В 1955-57 - 2-й секретарь Кустанайского обкома КП Казахстана.