Great idea!

Well, I got my first programming lessons on paper and it was very useful. You could draw "program"-flow graphs1 to bring the basics of abstraction nearer to them. Maybe you could also get some of the teachers and work out a little very easy language2 with words and a syntax which makes it easier for kids than a real language. You could also write a little parser if you wan't. If the language is easy enough it shouldn't be very hard with Modules like RecDescent. Although I've never worked with it and can't tell for sure.

Good luck! I hope this gave some good ideas.

1 Sorry, not a native speaker. Had a lack of a better word
2 Or maybe it already exists?