I learned Lisp aged 12, after messing around a bit with Basic. I consider myself very lucky for having had that experience. Writing an ELIZA clone at that age was a lot of fun - I remember in particular thinking it was hilarious to give my version a very rude personality ;-)

The original designers of Smalltalk taught a load of primary school kids to program. So squeak may be a good bet.

There was even a video on it. I think I saw this in one of Alan Kay's UI videos that are available here: http://webcast.berkeley.edu/course_details.php?seriesid=1906...