I don't know about complex pieces of software. But many algorithms were invented on paper first (or whiteboards.) Conway's game of life became popular before computers were programmed to do it, and people executed the moves with pencil on graph paper. Turing had a chess playing algorithm which he executed by hand on paper.

I've written short sections of code on a notebook before implementing it into a computer. It's slower, but it's possible, and I don't think paper is that inferior to a text editor. It will definitely require a lot more debugging when you finally implement it on a computer. So maybe write lots of test cases.