I was learning C when I was six years old. Definitely helped that my older brother (then 11) was the one teaching meβ I wonder if having young children learn from older children might be good advice in general?
I first coded when I was about the same age, but at that point it was mostly type out programs from magazines and making minor tweaks (this was in Atari Basic). When I was 9-10 I was writing my own simple games in Amiga Basic and later CanDo. When I was 13 I started learning K&R C and then later Quest-C (A VB like tool for C).
I remember there was one other kid in my year at school who was better at C than me at the time, so I don't think I was that unusual.
I think it easy to underestimate what kids are capable of.
I was typing out BASIC programs when I was around 6, got to love growing up with the Spectrum/C64 and the wonderful BBC Micro. I think it worked well; I still remember it being so magical (a since overused word sadly), and a lot of my early tweaking was PEEKing and POKEing around in games to cheat.
The OP has it right -- if you're doing something you want (building a Dr Who game, changing your high score, turning all the baddies into strawberries, making a spider run around the screen to scare your mum) that's the best, dare I say only, way to learn.
Having said this, nobody at my school could program at all (despite the BBC's best efforts). I didn't learn "real" programming until university; web scripting and PHP before that. Maybe that's why I'm such a hacky coder even now.