Learning programming without a computer is going to be really tough, but if he's dedicated enough, he should be able to make some good progress. (Although he shouldn't expect to be employable as soon as he gets out.)

CS theory probably makes a good starting point, as a lot of it doesn't require actual coding, but still lays a solid foundation for future work. I would recommend SICP (Structure and Interpretation of Computer Programs, by Abelson and Sussman) as a good starting point. It uses Scheme, which isn't exactly a language he's likely to end up working in, but it will teach him a whole lot about thinking like a programmer.