IMO 4 is too young. My oldest just turned 5 and I think it's more important for writing/spelling/math/computer usage vs coding skillz (she's able to read almost all 4-5 syllable words, and can kludge the spellings via sounds). Gain a base before looking at specifics. If the kid cannot read or write you can't program in the traditional sense...
If you do want to push traditional coding look at something that's not "coding" but rather a game: e.g. http://www.alice.org/
I like Will Wright's thoughts on the topic:http://vimeo.com/22670388
I personally just put up a bukkit server and make her interact via typing, but I won't make it easy: she first has to start MC with a shell script via terminal ^_^.
Eventually she, and her siblings, will gain the familiarity needed to out code me, but for now she can game on!