I would start with Common Lisp.
The Tandy/Radio Shack books for the Color Computer series (and it's astoundingly good LOGO implementation) were amazingly clear and concisely written with lots of examples, and because in those days even a disk drive wasn't a guarantee, all the examples were written to be hand-typed and experimented with.
There were even books in those days that aimed to teach kids machine language! 
That said, I think Djikstra and Felleisen may be slightly right about the long-term usefulness of old-fashioned BASIC and LOGO for learning, but there are a few books in modern languages that come close.
Hello World! was explicitly written to hearken back to those old manuals, by a father aiming to teach his 12-yo son programming with Python.
Land of Lisp and Realm of Racket also call to mind those old books as well, though they're targeting a bit older audience and have their quirks (LoL is a bit in-love with huge nested trees and a-lists in the examples, and Realm of Racket tends to gloss over a lot of the examples and expects you to just read the sample code rather than walking you through the process completely).
The Little Schemer is also a fantastic little book that takes on the form almost of a set of brain-teasers, and teaches recursive thinking entirely by example and in methodical detail. The later chapters can be a bit stumpy, but if you go through the book step by step in regular sessions it builds on itself pretty well.
All of these are aiming at around the 12+ age range though, I don't think there's much out there anymore for anything younger.
  
It's actually inspired by Conrad Barski's 'Casting SPELs in Lisp' (http://www.lisperati.com/casting.html), which in turn was inspired by Why's Guide to Ruby (I think). Conrad Barski actually wrote a Haskell comic book tutorial that predates 'Learn you a Haskell' (http://lisperati.com/haskell/). Not only that, but Conrad's full-length Lisp tutorial comic book, Land of Lisp, is due to hit the shelves in four days: http://www.amazon.com/Land-Lisp-Learn-Program-Game/dp/159327...