Do it more often!

Coding, whether with a computer or pen and paper, is one of those skills which is learned best by doing it more often. I’d start with working through problems on sites like Project Euler or Code Chef.

People usually do this in an interview when they want to see how you think.

Always make sure you have plenty of paper available, since you can’t correct mistakes the way you usually would. Be prepared to rewrite your program after making a rough draft.

I’ve also found that using diagrams like structure charts, or Warnier-Orr diagrams, helps me clarify my though processes.

If you want to try this with some simple programs to get some practice, I suggest Project Euler as a source of such program exercises. They are usually mathematically interesting!

Oh, and add lots of comments. More than you usually would. Remember, the potential employer is trying to see how you think – try to give them insight into your thought processes.

turn off the computer, grab pencils, paper, and an eraser, and get writing code.
Then, review it rigorously using references and try to prove its correctness.
Only when that’s all done, sit down, type it in, compile and run to verify you got it right.
There is no other way.

While I applaud you for your ambitious(odd) dedication, I’m not so sure that pen and paper are the best solution for programming mastery. I would suggest learning to code in MS Notepad though. This is just my opinion, obviously, but I learned HTML/CSS/JavaScript in notepad and everything became muscle memory very fast. I actually got a contract job simply for putting ht/cs/js (using notepad) on my resume. I have also done ‘some’ C#.Net in notepad using the command-line compiler, and it’s not so bad. Don’t recommend it though.

My two cents.