I started shooting on the original Olympus XA at 6. At the time getting film developed was expensive, so there was the added challenge of not wasting any of it.
I think the cheapest point and shoot will be nice. It doesn't need manual controls either, they will find ways to get around the limitations and learn something in the process. Then, if they really are serious, they will ask for something more flexible.
Another solution, that is fun but kind of expensive (because of the prints) is the Polaroid Snap Touch (get the Touch version, very important). It's like the Fuji Instax, but shoots in digital and lets you print only what you want. It's not flimsy, but obviously will need more care than a cheap point and shoot.