First thing, don't underestimate kids' ability to learn new things, it is important to keep them challenged.
I would recommend,
http://www.greenteapress.com/thinkpython/thinkpython.pdf
Python got the turtle, so no need for logo.
Videos makes things easy.
http://showmedo.com/videos/python
Games are also a great motivator.
When (s)he gets more advanched, older (think: upgrade path) I would recommend things like,