As a teenager in the 80s I did learn mostly on paper at first -- no computer for the first year and more. The maybe nonobvious benefit, if you're lucky in your choice of books, is in coming to expect code to be as nice and pretty as the textbook examples. The working world was quite a comedown later on.

Maybe a crazy idea, but Dijkstra's A Discipline of Programming was meant for coding on paper. Hehner's A Practical Theory of Programming is kind of similar and more recent -- I haven't read it.