Był synem zniemczonego Czecha Wacława Scheinoha-Vtelenský'ego i Marii z Łozińskich (jego kuzynami byli pisarze Walery i Władysław Łozińscy). Ojciec Szajnochy, z wykształcenia lekarz, porzucił zawód medyczny i osiadł w Galicji jako tzw. mandatariusz. Nie wysługiwał się władzom austriackim, zżył się ze społeczeństwem polskim, nauczył się mówić po polsku, ożenił się z Polką i spolszczył tak dalece, że dzieci wychował na Polaków. Polakiem czuł się od lat najmłodszych Karol, który początki nauki pobierał w domu, a następnie uczęszczał do szkół średnich w Samborze i we Lwowie. W szkole średniej starał się zatrzeć ślady swego niepolskiego pochodzenia, zmieniając stopniowo pisownię nazwiska (Scheynoha de Wtellensky, później Szejnoha de Wtellensky, wreszcie Szajnocha).

W 1834, w gronie kolegów szkolnych założył konspiracyjne „Towarzystwo Starożytności” mające na celu gromadzenie i referowanie wiadomości o istniejących w kraju zabytkach przeszłości. członkami jego byli nie tylko uczniowie Polacy, ale również, i to w większości, Niemcy i Rusini. Sprawa się wydała, przeprowadzono śledztwo, w którym Szajnocha całą odpowiedzialność wziął na siebie. Kara nie była zbyt dotkliwa, jednak miała brzemienne skutki w przyszłości. 

W 1835 zapisał się na Wydział Filozoficzny Uniwersytetu Lwowskiego, ale po kilku miesiącach, 21 stycznia 1836 został aresztowany i odstawiony do więzienia śledczego. Oskarżony był o pisanie kartek i wierszy o antyrządowej treści. Kartki te znaleziono na uniwersytecie i w kościele bernardyńskim w ławkach, które podczas mszy szkolnej zajmowali uczniowie najwyższej klasy gimnazjalnej. Szajnocha i tym razem przyznał się do winy.

Został aresztowany i osadzony najpierw w zwyczajnym więzieniu, jednak po kilku tygodniach przeniesiono go do więzienia specjalnego i tam trzymano go w kajdanach założonych na nogi i ręce, w zupełnej ciemności. Nie dawano mu przy tym ani światła, ani książek. Stęchłe powietrze, ustawiczna wilgoć i mrok oddziaływały szkodliwie na jego młody organizm. Dla zapełnienia rozpaczliwej bezczynności, w czasie gdy było coś w celi widać, wyrabiał sobie igły z kości i drutu siatkowego, wydobywał nitki z prześcieradła lub szpilką pisał na ścianie utwory poetyckie, w wyniku czego osłabił sobie na stałe wzrok. W ciężkim więzieniu Szajnocha przebywał do połowy 1837.