Николай Васильевич родился в 1846 г. в Пензе, в семье чиновника, носившего чин титулярного советника. Он окончил Пензенскую гимназию и поступил на физико-математический факультет Петербургского университета. Однако получить высшее образование ему не довелось, со второго курса Клеточников был вынужден уйти по состоянию здоровья – открылся туберкулез (еще одна профессиональная болезнь русской интеллигенции). Ему пришлось уехать в Крым и сделаться там чиновником. В 1877 г. он вернулся в Петербург и стал вольнослушателем Медико-хирургической академии, но вскоре туберкулезный процесс открылся у него вновь. Понимая, что жить ему осталось недолго и желая провести остаток дней с пользой для общества, Николай Васильевич с октября 1878 г. ищет выходы на революционеров. Через месяц с помощью слушательниц Бестужевских курсов он знакомится с А.Д. Михайловым.
Одному из руководителей радикалов понравился этот человек – среднего роста, худой, немного сутулый, с редкими каштановыми волосами, тронутыми на висках сединой, с умными, усталыми глазами. Михайлов предложил Николаю Васильевичу проверить одну «мутную» домовладелицу. А.П. Кутузова сдавала комнаты студентам и курсисткам, а вскоре после найма комнат некоторых из них арестовывали и высылали. Клеточников поселился в доме Кутузовой и быстро вошел к ней в доверие. Тихий жилец любил вечерами почаевничать и перекинуться в картишки. При этом Клеточников, изображавший провинциала, приехавшего в столицу в поисках хорошего места службы, постоянно проигрывал хозяйке в карты по 2–3 рубля. В конце концов, Кутузова сама предложила устроить жильца в III отделение, где немалый пост занимал ее племянник полковник В.А. Гусев. Задание подпольщиков, таким образом, было выполнено, но для Клеточникова все только начиналось.
Михайлов ухватился за предложение Кутузовой обеими руками, его давнишней мечтой было завести «своего» человека в III отделении. Клеточникова же после разговора с Александром Дмитриевичем охватила неподдельная паника. По его словам: «Из всех невозможных невозможностей эта была самая невозможная». Однако Михайлов сумел уговорить его, доказав, что подобная деятельность важнее взорванного Зимнего дворца или даже убийства императора. По протекции своей домохозяйки Николая Васильевича приняли в III отделение в качестве одного из многочисленных агентов, наблюдавших за благонамеренностью студенчества. Три раза в неделю он должен был докладывать начальству о своих успехах на новом поприще. Получал он за это по 1 рублю в день, то есть по 30 руб. в месяц (видимо, в память о 30 сребрениках, вырученных Иудой за предательство Христа).
Только успехов-то у него и не наблюдалось. Клеточников раз от раза приходил с пустыми руками, ссылаясь на сильную близорукость (что было правдой) и на свое чуть ли не физическое отвращение к людям, разделявшим «подрывные» идеи (что являлось отъявленной ложью). Начальство уже подумывало о том, чтобы под благосклонным предлогом избавиться от незадачливого агента, но тому помог случай. Замещая заболевшего писаря, Клеточников заполнил несколько документов, после чего его карьера в III отделении была обеспечена. Каллиграфический почерк нового агента привел всех в восторг.
Вскоре Николай Васильевич был назначен письмоводителем агентурной части 3-й экспедиции III отделения. Его добросовестная служба не раз отмечалась начальством денежными премиями, приглашениями на званые вечера и даже орденом Св. Станислава 3-й степени. После ареста контрразведчика растерянное начальство 3-й экспедиции выдало ему вполне позитивную характеристику, в которой значился следующий пассаж: «В продолжение всей своей службы отличался особенным усердием и пользовался доверием начальства». А как Клеточникову было не усердствовать?