Фамилия Холодулькин — редкий случай, когда в основе лежит не имя, не профессия и не географическое название, а, скорее всего, прозвище, связанное с погодой или характером.

Разбираем словообразовательную цепочку. Суффикс -ин указывает на принадлежность: Холодулькин — сын Холодульки. Само прозвище Холодулька образовано от слова «холод» с помощью уменьшительно-ласкательного суффикса -ульк- (сравните: дочка — дочулька, зима — зимулька). То есть Холодулька — это не просто «холодный», а скорее «холодок», «холоднушка». Такая форма в русских говорах могла относиться к человеку с прохладным, бесстрастным нравом, либо к тому, кто постоянно мёрз и кутался, либо к ребёнку, родившемуся в холодное время года.

Версия, что фамилия происходит от названия блюда («холодец» и его диалектных вариантов), менее вероятна. Хотя в некоторых говорах «холодулька» могла означать студень или окрошку, но прозвище по еде обычно образуется напрямую (Холодец, Холодник), а не через уменьшительную форму с оттенком ласкательности. Гораздо логичнее, что прозвище дали человеку за его «температуру» — внешнюю или внутреннюю.

Фамилия явно недворянская, не искусственная (вроде семинарских), а бытовая, крестьянская или мещанская. Встречается она в основном в центральных и северных областях России, где зимы долгие и холодные. Носители фамилии Холодулькин — потомки того самого Холодульки, которого когда-то в деревне прозвали за зябкость, суровость или просто за то, что он появился на свет в крещенские морозы.