Whatever language you choose: write a lot of (small?) shell scripts. This is very unix-y and also easy. The composing of those scripts using unix-pipes also will give him a little bit experience with things like modularity.
Also, I'd choose a language I like and that I'm familiar with. I think OCaml would definitely be a good start. Strongly typed and strict, lots of possibilities for abstraction, it's all pretty cool. Or teach him (and yourself) Haskell using RWH or something.
If you go for an imperative language then Ruby or Python would probably be a good idea. Those languages are really a lot like English and have a lot of momentum. If you go for Ruby, take a look at http://hackety.org/, I think it's awesome for young programmers.
Also, I'd choose a language I like and that I'm familiar with. I think OCaml would definitely be a good start. Strongly typed and strict, lots of possibilities for abstraction, it's all pretty cool. Or teach him (and yourself) Haskell using RWH or something.
If you go for an imperative language then Ruby or Python would probably be a good idea. Those languages are really a lot like English and have a lot of momentum. If you go for Ruby, take a look at http://hackety.org/, I think it's awesome for young programmers.