I thought about a cheap p&s. It would be less to worry about and simpler to use. I was just concerned that p&s cameras are so unresponsive that he might get discouraged. I also liked the idea of having him use something that worked essentially the same way as his parent's camera. I find that kids pick up a lot through watching.
What about an "advanced" P&S camera: like a Canon S3, Sony H7/H9 or Fuji S9000?
All of them are very responsive (very little shutter lag, and continuous speeds as fast as 2.6fps), bigger than a fit-in-your-pocket P&S but smaller than a DSLR, and all have Manual modes very similar to a DSLR. I can't imagine any kid being dissatisfied with one of these ... I'm almost 40 and I love mine!
They've all got wide-angle, zoom and macro without needing to change lenses, so no chance of getting dirt on the sensor.
They also cost less than some of the *lenses* you'd put on a DLSR!
I think I would start with composition and Auto ... kids often have a different view on things, and training/developing his photographer's eye from such a young age could be a very good thing. You could easily break him into the complexities of exposure through the Av and Tv modes on the way to full Manual. No need to dump the "mechanics" on a budding artist anyway....
You also mention learning by watching ... but changes are he's going to be shooting what you shoot, not looking over you shoulder to see what settings you're choosing. He's going to think "Daddy's shooting the castle, so I'll shot the castle, too." I doubt, at 1st grade, he'd be wondering what aperture and shutter-speed you've set....