Происходил из дворян Московской губернии, сын участника Наполеоновских и русско-турецких войн, генерала Н. И. Шелашникова; родился в 1820 г. По окончании первоначального образования в школе гвардейских подпрапорщиков и кавалерийских юнкеров Шелашников был произведён в подпрапорщики, 22 декабря 1837 г., с зачислением в Лейб-гвардии Семёновский полк и через два года, в 1839 г. 28 декабря, получил чин прапорщика со старшинством с 1 октября 1838 г.
В феврале 1844 г., Высочайшим повелением, он был командирован на Кавказ в Апшеронский пехотный полк для участия в одной из экспедиций, снаряженных против горцев под начальством генерала от инфантерии Лидерса. Прибыв в начале мая к месту своего назначения, Шелашников тотчас же вступил в состав Дагестанского отряда, авангард которого, под предводительством генерал-майора Пассека, занял селения Дурголи и Дженгутай; подвигаясь по направлению к Параульским высотам, небольшой отряд одержал блистательную победу над огромным скопищем горцев, остатки которого русские преследовали до селения Кака-Шуры. В августе Шелашников участвовал в экспедиции генерал-майора Пассека, снаряженной против Салатовского общества, находился в стычках и перестрелках с горцами в окрестностях аулов Нового и Старого Буртуная, был при сожжении с. Зубуту, истреблении моста через Сулак и только 3 октября вернулся в укрепление Темир-Хан-Шуру.
16 марта 1845 года Шелашников возвратился в Семёновский полк, 11 апреля 1848 г. был произведён в штабс-капитаны, 6 декабря 1849 г. в капитаны, а Высочайшим приказом от 28 апреля 1851 года назначен дежурным штаб-офицером войск, расположенных в Восточной Сибири, с зачислением по армии подполковником. В новой должности Шелашников сумел обратить на себя внимание начальства.
9 декабря 1852 г. был награждён за отличие по службе чином полковника, в октябре 1856 года назначен бригадным командиром Иркутского и Енисейского казачьих полков.
Произведённый в апреле 1859 г. в генерал-майоры, Шелашников в следующем, 1860 г. был назначен председателем комитета для составления положения о казачьих войсках Восточной Сибири. В 1863 году Шелашников временно исправлял должность военного губернатора Забайкальской области и наказного атамана Забайкальского казачьего войска, в январе 1864 г. назначен военным губернатором города Иркутска и Иркутским гражданским губернатором; в августе 1865 г. произведён в генерал-лейтенанты.
С 1 сентября по 7 декабря 1879 г. Шелашников исправлял должность генерал-губернатора Восточной Сибири, а в апреле 1880 г. был отчислен от должности Иркутского губернатора с зачислением в запасные войска.
Спустя год, в 1881 г., он был назначен в распоряжение командующего войсками Харьковского военного округа, а в октябре 1882 года зачислен в запас армии. Последнее время Шелашников жил в Санкт-Петербурге, где и скончался 31 января 1888 г., похоронен на кладбище Новодевичьего монастыря
Значительная часть службы Константина Николаевича была посвящена административной деятельности в Восточной Сибири. Во время его губернаторства в Иркутске были открыты: отделение Государственного Банка (в 1865 г.), общественная реальная прогимназия, преобразованная потом в техническое училище; сиропитательная ремесленная школа (в 1866 г.); детский сад (в 1869 г.); учительская семинария, городская управа и введено городовое положение (в 1872 г.), открыт Сибиряковский приют для бедных, окончен и открыт Новый театр (в 1873 г.); женское училище преобразовано в женскую гимназию; ремесленная школа почётного гражданина Никанора Трапезникова; Иркутское юнкерское училище (в 1874 г.): заложен новый громадный кафедральный собор (в 1875 г.).
