Гавриил Степанович Батеньков родился в семье дворянина обер-офицера Степана Герасимовича Батенькова (около 1738–1808). Мать его – урожденная Урванцева. Гавриил был двадцатым ребенком в семье. То, что к моменту его рождения родители были весьма немолоды, сказалось на здоровье Батенькова. Родился он «почти мертвым», по легенде, только при похоронах, уже в гробике, обнаружилось, что младенец живой. С детства Гавриил отличался чрезвычайной нервностью, был близорук, хотя обходился без очков, был слаб голосом, а услышанный в детстве звук большого колокола расстроил его слух. Воспитывался Батеньков в Тобольском военно-сиротском отделении, потом в народном училище и гимназии, а также в Дворянском полку при 2-м кадетском корпусе в Петербурге. Оттуда в мае 1812 года Батеньков был выпущен прапорщиком в 13-ю артиллерийскую бригаду.
Батеньков участвовал в Отечественной войне 1812 года и заграничных походах. 17 декабря 1813 года за отличие он был произведён в подпоручики. 20 января (1 февраля) 1814 года Батенькова наградили орденом Святого Владимира 4-й степени с бантом – за отличие в бою при селении Ларотьер. В сражении при Монмирале 30 января (11 февраля) 1814 года был ранен (получил 10 штыковых ран) и попал в плен, в котором находился до 10 (22) февраля 1814 года. С сентября 1814 года служил в 27-й артиллерийской бригаде, с 11 января 1816 года – в 14-й батарейной роте 7-й бригады. 7 мая 1816 года уволен с военной службы по состоянию здоровья (последствия ранений).
Сдал экзамен в Институте Корпуса инженеров путей сообщения и с 5 октября 1816 года назначен инженером 3-го класса в Х (Сибирский) округ, 2 февраля 1817 года утверждён в чине поручика. В марте 1817 года Батеньков приехал в Томск, где возглавил работы по благоустройству улиц (строительство гравийных шоссе вместо полусгнивших деревянных мостовых), водоисточников, по укреплению набережной реки Ушайки и возведению деревянного Думского моста через неё. В аттестате, выданном губернатором перед отъездом, говорилось, что Батеньков «в короткое время… показал на пользу города Томска довольно успеха усердным своим старанием, деятельными всегда занятиями и искусством». В Иркутске в 1819–1821 годах он был ближайшим помощником генерал-губернатора Михаила Михайловича Сперанского по управлению Сибирью. В 1821 году Батеньков был произведен в майоры.
28 июля 1821 года он был назначен в Особый сибирский комитет с переводом в Петербург. 29 января 1823 года Батеньков стал чиновником по особым поручениям по части военных поселений, а затем – членом Совета главного над военными поселениями начальника Алексея Андреевича Аракчеева. 25 января 1824 года он был произведён в подполковники. С 10 июля 1824 года Батеньков – старший член Комитета по отделениям военных кантонистов. Он разработал устав об управлении инородцев, определявший правовой статус и внутреннее самоуправление коренных народов Сибири до самой Февральской революции. В 1825 году Батеньков вышел в отставку вследствие разных неприятностей по службе. В середине ноября начальник штаба военных поселений Петр Андреевич Клейнмихель (1793–1869) получил анонимный донос (т. н. «Записку об истинном и достоверном»), где подробно излагалось мнение Батенькова об убийстве Минкиной, любовницы Аракчеева: «Тогда как все почти изумлялись и считали происшествие сие ужасным поступком, Батенков изъяснялся об нем в разных шутках, в разных насмешках и всегда в веселом духе. Правда, что сие делал он неоткрыто. <…> На сожаление и удивление, по сему страшному происшествию изъявляемое, говорил он: «Не нужно жалеть! вещи идут своим ходом. Несчастие невелико; впрочем, несчастие одних есть счастие для других. <…> Стояние вещей в одном положении невыгодно – в обществе и вредно. Что за беда, что Настасьи не стало, и есть ли о чем жалеть?» В сем месте его разговора изъяснял он о покойной Настасье Федоровне разные нелепости, и столько распространялся в самых язвительных насмешках, что человеку благородно мыслящему невозможно слышать без досады, которая и во мне произошла к Батенкову, видя его в столь развратных, подлых и бессовестных мыслях. Потом, обратя разговор о графе, говорил: «Не беспокойтесь! Если случай сей расстроил графское здоровье и силы, то вместо графа Алексея Андреевича найдется другой граф Сидор Карпович, и при нем, может быть, и нам еще лучше будет. Например, – сказал он, – если таковой случай приблизит по-прежнему к Государю нашего хозяина (хозяином разумел Сперанского, у которого живет он, Батенков, и с ним привезенные из Сибири), то мы, без сомнения, не проиграли бы, а были бы весьма рады»