Hi! I work at a "Young Researchers Centre", a sort of after-school crafts-and-technology place for kids of roughly ages 8-12. They can work wood carpentry, clay pottery, fabric, metalworks (lots of cute jewelry made from resistors :) ), electronics/soldering, Lego Mindstorms and of course computers. I supervise at the last two.
We don't let them play webgames, YouTube, Facebook or Pokemon websites or things like that, except for the final 30 minutes which is free time (though I still won't let them on Facebook--that's a hairy situation I'll let the parents sort out responsibility over at home. I believe the webfilter blocks it too).
Anyway, what they can do: Creating animations with a stick-figure animation program called Pivot, build plain HTML+images websites (with jEdit free syntax highlighting editor that also works over FTP) and create games with the free trial of Gamemaker (GUI-based point-and-click programming, not bad at all). Oh and this afternoon I helped a little guy shoop fake Pokemon cards in GIMP :-)
We are looking at introducing a little bit more actual programming into the possibilities, though. I visited this very same centre at the age of ten, and I'd just fire up QBASIC and start coding funky graphics, and there were at least one or two other kids that did similar.
My personal experience is that level of ability varies a lot with age, they develop real quick in this age-range. I wouldn't try and teach an 8 year old to program, not even with GameMaker. For some reason kids that age do not yet seem to have developed this hyper-interested bite-your-teeth-in-it persistence (you probably know what I'm talking about if you started coding at a young age--it's amazing, even if the smartest ones are invariably also super annoying clever little know-it-alls, which I try my best to not let get in the way of teaching them :) ).
I did have success with helping an 8 year old kid write his own webpage in HTML. His writing skills were phenomenal for his age, very little spelling errors, just needed to learn proper capitalisation and use of the comma :-) Capitalisation is probably also a result of not yet fully developed motor skills at that age, you can tell that pressing shift with their other hand actually takes them effort. Anyway, he wrote a short introduction about himself and proceeded to write a number of (actually quite funny) jokes and puns. I hope he returns soon, so we can add some styling to the page, it's just plain black-on-white Times with H1, H2 and P tags now.
One important thing we try to focus on here, is to give the kids something to do they can actually finish or at least see some tangible results of within one afternoon. It's really demotivating to be real busy for a couple of hours and not have something bounce around your screen at the end of it, preferably as soon as possible.
Another important thing is, that it's not school. They're not graded and they don't have to do things perfectly, or even the right way. The kids at electronics are soldering wires onto thumbtacks pushed into a piece of soft wood (with a paper printed diagram pasted on it, they make flashing lightbulbs, simple radios etc). It's very easy and it works, but it's not a proper way to do electronics :) In a similar fashion, I'm not going to push them to write properly CSS-ed content-layout-separated semantic HTML. If it's easier and simpler to use an inline style, or even a TABLE based layout, I'll show them how to do it. It's more important to show them how to get their hands "dirty" and that they can make these computers do anything they want, I like to show them quick results and they can always learn to do things the proper way later on.
On that note, I realize that PHP is probably the best way to get them started in programming. Most kids can get the hang of HTML pretty quickly (what are the tags for, opening and closing tags, how do you make an image, a link, etc). PHP has the nice property that you can just write it inside the HTML and easily add a little bit of interactivity, with immediate results. Indeed no templating languages, and yes it will grow into a huge tangled mess as they add more and more complexity BUT if there's one young these young kids are very good at, it's keeping track of a tangled mess of their own creation.
A simple example, one kid wrote a multi-page HTML website, with a menu bar (just a line of link tags) on top to navigate. What sucks for him is that he has to duplicate the menu code in every HTML page, and if anything changes or he wants to add another menu-link, he has to edit them all. There's no way to solve this in HTML, except with a FRAMESET which is kinda complex (and very outdated). So next time I will show him how, with a single line of <?php include('menubar.html'); ?> he can make things a lot easier for himself. It's still not real programming, but yet another small step along the way, that delivers immediate results.
Finally, a completely different idea I had, is to show them how to make simple games with Python and PyGame. IMO, Python is one of the best languages to start out with (I suppose Ruby is also pretty great but I'm not too familiar with it), and PyGame is real easy to use as it has functions for images, sprites, timing and even collision detection. I would start them off with a basic skeleton that opens a window and an event loop and possibly some object moving around or something. I'm not really sure whether I'll pursue this idea, because currently the "ease-them-into-PHP" idea sounds better, and I only have so much time to prepare new things :)
So, I can only share my experiences, unfortunately not offer much concrete advice, as we're still trying to figure out the best way as well.
(BTW myself, I started with BASIC at the age of 9. Reasonable beginners language, but it was also the only choice available for me :) )