I recently listened to an interview with Leslie Lamport where he said you should write a description of your program in prose before writing any code. So not exactly programming on paper, but part of the process of thinking about what you're going to do can be captured on paper.

He has a saying I like, "If you think without writing you only think you're thinking"