Николай Васильевич родился в семье архитектора Пензенской казенной палаты. В 1864 году он поступил на физико-математический факультет Петербургского университета, однако в 1866 году врачи признали у него чахотку, и учебу он бросил. Для поправки здоровья Клеточников отправился в Ялту, где поступил на службу. Получив в 1873 году небольшое наследство, он «прожил» его за границей и вернулся оттуда с решимостью принять участие в революционной борьбе. Его землячки – слушательницы Бестужевских курсов – свели Николай Васильевича с членами Исполнительного комитета «Народной воли» Александром Дмитриевичем Михайловым (1855–1884) и Николаем Александровичем Морозовым (1854–1946).
Из воспоминаний Н.А. Морозова: