I started my 6 year old daughter on Scratch. I think it will fill the bill for your son. It's very visual and includes enough control structures to allow you to make real programs (games and media presentations are its forte.)
There may also be some good puzzle games around which teach relevant skills. Boolean algebra, stuff like that.
Simple programmable robots are also good, like the old LEGO turtle. If it's accessible, kids will often self-determine things they want to make it do and then work at it until it happens (provided they don't get stuck too badly).
http://scratch.mit.edu/
Now that she's 8 and has a better understanding of math she's moved on to http://inventwithpython.com/