I'd probably go with a cheap digital rather than a film. They tend to take pictues of lots of stuff and film-based would be wasteful. I'd also stay away from P&S where the lens sticks out too long when you turn them ON. Also the weight could be an issue, most cheap digicams are bulky and are pretty heavy.
I bought my niece the Canon A520 last year, but she's much older than 4. It's a lightweight and relatively small.
Check out Steve's best cams and make sure you go to a store so she can hand hold it and she'll feel comfortable with it.
http://www.steves-digicams.com/best_cameras.html