My nephew and I have had some success with "Hello World! Computer Programming for Kids and Other Beginners". Many parts of the book direct the student to try out the examples in the interpreter, which I think is a nice way of demonstrating the concepts immediately. It starts with strings and other basics, and gets gradually more complex. By the end of the book you will have "written" a basic skiing game with pygame.

http://www.amazon.com/Hello-World-Computer-Programming-Begin...