I'm thinking about that too.
One of the problems I face is the lack of good books for children in german, though here is a good reading about that.

Another point is keeping the tasks interesting. footpad made some good points here.
25 years ago I was happy programming space invaders in ASCII but times have changed.
Kids like to do something graphically and that's not easy in perl, so I even considered switching to java.

Further reading: Perl as a first language, Not-So-FAQ about learning Perl