Родился в подмосковном селе Преображенском, где его отец служил придворным конюхом. Как и другой будущий кораблестроитель Федосей Скляев, он четырёхлетним ребёнком был зачислен в «Петров полк» и с детских лет подружился с юным царевичем. В 1695 г. он как бомбардир Преображенского полка входил в 4-ю роту «каравана» первого Азовского похода, которой командовал сам царь, Гаврила Меншиков в этом походе был в должности боцмана на одном из судов, а в следующем, 1696 г. во время второго Азовского похода — боцманом на галере «Принципиум», следовавшей под командованием самого Петра.
Г. А. Меншикова царь сам лично включил в списки волонтеров при Великом посольстве, когда оно в 1697 г. отправлялось за границу. Вместе с Федосеем Скляевым, Лукьяном Верещагиным, Александром Меншиковым, Иваном Головиным, Иваном Кочетом и другими преображенцами Гаврила Меншиков неотлучно находился при Петре, работая корабельным плотником на верфи Ост-Индской компании и обучаясь там кораблестроению у мастера Герита Класа Поля.
Побывав на верфях Англии и Венеции, по возвращении из-за границы Гаврила Меншиков в числе других учеников корабельного баса Петра Михайлова работал в Воронеже на постройке кораблей в качестве подмастерья у корабельных мастеров-англичан. Вплоть до 1704 г. Гаврила Меншиков находился в Воронеже, где помогал Федосею Скляеву строить 50-пушечный «государев» корабль «Ластка», «государеву» яхту «Либе» и две большие камели для проводки на них кораблей к Азову.
Завершив эту работу, Меншиков отбыл со Скляевым в Санкт-Петербург, а затем на реку Лугу, где впервые самостоятельно стал строить скампавеи и другие суда для галерной эскадры Балтийского флота. Затем вместе с голландцем Вуотепом Вуотерсеном он строил на Сясьской верфи 28-пушечный фрегат «Иван-город», а после слияния этой верфи с Олонецкой стал строить там разные суда вместе со Скляевым и английским корабельным мастером Броуном.
В начале XVIII в. Гаврила Меншиков, хотя ещё официально не был не только корабельным мастером, но даже и подмастерьем, продолжая числиться всего-навсего корабельным учеником (известно, как скупо Петр жаловал званиями даже своих любимцев!), получал жалование под стать квалифицированному мастеру — 180 рублей в год. Лишь Федосей Скляев из отечественных кораблестроителей в ту пору получал больше — 200 рублей в год (позднее он стал получать 1396 рублей в год). В 1706 г. Гаврила Меншиков работал в Санкт-Петербургском Адмиралтействе, помогая Скляеву строить яхту «Надежда», а затем сам построил на Галерной верфи опытную 22-баночную галеру, о маневренных качествах которой хорошо отозвался сам Петр.