Николай Герасимович Володченко родился в Санкт-Петербурге 20 ноября 1862 года, был православного вероисповедания. Он был сыном надворного советника. Образование получил в 3-й Санкт-Петербургской военной гимназии, по окончании которой 1 сентября 1881 года был зачислен в Михайловское артиллерийское училище. Выпущен 14 августа 1884 года подпоручиком в 1-ю резервную артиллерийскую бригаду.

В 1886 году был произведен в поручики со старшинством в чине с 7 августа 1886 года. В 1889 году Володченко успешно сдал вступительные экзамены в Николаевскую академию Генерального штаба, откуда был выпущен в 1892 году по 1-му разряду, причём, за успехи в науках, был произведён в штабс-капитаны со старшинством с 6 мая 1892 года и причислен к Генеральному штабу. Был назначен состоять при штабе Виленского военного округа.

26 ноября 1892 года был переведен в Генеральный штаб с назначением старшим адъютантом штаба 2-й кавалерийской дивизии, 17 апреля 1894 года произведен в капитаны. С 1 октября 1897 года по 1 октября 1894 года проходил цензовое командование эскадроном в 6-м лейб-драгунском Павлоградском полку. Произведённый 18 апреля 1899 года в подполковники, Володченко тогда же был назначен старшим адъютантом штаба Виленского военного округа; с 16 января 1901 года состоял штаб-офицером для поручений при командующем войсками Виленского военного округа.

В 1917 году был главнокомандующим Юго-Западным фронтом. После начала Первой мировой войны, при мобилизации, Володченко 2 августа 1914 года был назначен командиром бригады 3-й Донской казачьей дивизии; в ноябрьских боях 1914 года командовал самой этой дивизией. С 26 апреля 1915 года являлся командующим (позже начальником) 16-й кавалерийской дивизии. За боевые отличия 16 июня 1915 года был произведен в генерал-лейтенанты.

В 1919 году Володченко эвакуировался на Дальний Восток, состоял сначала в армии Восточного фронта, затем начальником внутренней охраны полиции КВЖД. Жил эмигрантом в Харбине, опубликовал несколько статей в крупнейшем журнале русской эмиграции «Часовой». Был активным деятелем в русской военной эмиграции в Маньчжурии и одно время открыто претендовал на официальное руководство в ней. 24 сентября 1945 года был арестован органами СМЕРШ по обвинению в антисоветской деятельности и в конце года (по другим данным — в 1946 году) скончался в заключении во время следствия. По заключению прокуратуры Омской области от 22 ноября 1999 года был посмертно реабилитирован.