Военную службу Василий Храмченко начал задолго до Великой Отечественной войны, в 1929 году. Тогда его после окончания рабфака призвали в Красную Армию. В 1931 году он окончил Рязанскую пехотную школу, в 1932 году - Саратовскую танковую школу, в 1934 году - Борисоглебскую школу летчиков имени Чкалова. Командовал сначала взводом 163-го образцового полка в Белгороде, потом танковым взводом, был командиром звена в авиачастях в Баку и Тбилиси, командовал авиаэскадрильями в Борисоглебской, Львовской и Черниговской авиашколах.

Свою первую боевую награду Василий Храмченко получил, в 1937 году. Тогда им успешно было выполнено задание Генерального штаба Красной Армии по фотографированию ирано-иракской границы - это свыше 7,5 тысяч квадратных километров территории.
А своего первого немца Храмченко сбил на рассвете 22 июня 1941 года.  Он часто вспоминал этот воздушный бой: "Это было в Чернигове. Я командовал эскадрильей, сформированной авиационной школой. Готовились к открытию учебных лагерей на аэродроме "Пески". Около 4 часов утра мы с дежурным проверяли, все ли готово. Вдруг услышали в небе гул приближающихся самолетов, а затем увидели с запада и сами бомбардировщики. Они приближались к нашему аэродрому. Это были немецкие самолеты "Хейнкель-111". Их было 27. Летели клином - три девятки. Внезапно одна девятка отстала от других и стала перестраиваться. Другие самолеты улетели дальше. От оставшихся самолетов отделились черные точки. Неужели бомбы, промелькнула страшная догадка. И в самом деле! Да ведь это же война!\"
Храмченко побежал к своему истребителю. Взлетел. Вражеские бомбардировщики дважды бомбили мост через Десну, но им не удалось разбить его. Храмченко делал все возможное, и, когда расстояние до первого самолета сократилось до 100 метров, он неожиданно для врага вынырнул из облаков и дал длинную очередь по ведущему "хейнкелю". Тот вспыхнул.
Когда стал заходить на второй - увидел, что на него устремились все восемь оставшихся бомбардировщиков. Завязалась перестрелка. Из одного самолета пошел дым, но он продолжал лететь.