When I was a kid I used to bitch about game censorship, but to be fair I think I was about 13 by the time a game dropped an f bomb on consoles, flash forward a bit, and now I have a 6 year old son, who is ravenous about games, and robots, and zombies, and explosions. It makes for a difficult situation, one that I think each parent has to really weigh themselves. I still bitch about censorship, but am thankful for things like ratings, and wish they were a little more thorough... I'm in the UK, and the bbfc do an ok job, but  terms like 'moderate violence' covers a lot of ground. Being a fan of games as well, it's easy for me to pick up a controller and use my own good judgement to decide, or in best case, sit and actually play with him, ( even if that means I may have to see the ending to Lego Star Wars a few too many times...).  
 
One thing I have noticed is my son is really taking a liking to open world games, which is sadly a genre that tends to skew more towards the adult end of the spectrum, Just Cause 1 and 2 weren't too bad (under supervision, and avoiding certain areas) and Burnout paradise was perfect. I just wish there were more games that allowed him to explore an environment, without all the 'grit'. As I side note does anyone else have any other suggestions? 

Burnout Paradise is a possibility. The recent Prince of Persia might also be worth checking out. Is there any particular platform your son plays on?

Yeah in terms of game censorship, I hope to see it enforced alot more than it currently is. Not so much to protect our children but to help games be taken seriously or at least on the same level as films. Also some kids are better about violent games than others. I know that none of my friends have been affected by violent videogames but this matter needs to be gaged on a case by case basis and I'm glad parents like yourself are doing just that :) 
As for your question, I'm afraid I can't provide any recommendations of non violent open world games off the top of my head... It seems open world also encompasses what you can do in that game world which sadly includes violence :S

" Burnout Paradise is a possibility. The recent Prince of Persia might also be worth checking out. Is there any particular platform your son plays on? "

Wow. Can't believe I forgot about Banjo-Kazooie. Definitely pick that one up.

Might as well make use of it! 
http://www.giantbomb.com/open-world/92-207/ 
Edit: the Skate games are open world 
Bully as well (if you don't count playground violence :) )

Since you're fighting enemies spawned by the dark god Ahriman, not blood or anything like that. Just healthbars and a disappearing animation. Here's a vid link to some gameplay: http://www.youtube.com/watch?v=jw5NnQoYi5A

The only time you fight humans is toward the beginning/tutorial part. As far as I can remember, there's no blood or gory kills.

" @swamplord666: Its true, I've yet to see one without violence, its a shame they cant make a Crackdown / Mirror's edge experience based purely on exploration My son used to play just the traversal part of Infamous, (and currently does in Just Cause 2) and hands the controller across if anyone 'bothers him'. That being said I had a bit of a dilemma in JC2 when the police attacked him and he stopped to ask if that meant he was a bad guy... I started trying to explain corruption, and lastly decided to state there was a misunderstanding. "

I haven't played one in a while, but I remember the Pokemon games being pretty open-world and plenty kid friendly (if he has a DS). The sense of exploration is a bit different than in a 3D game world, but worth a thought. 
 
Also, what about something like The Sims? It's not open-world the traditional sense, but it certainly is open to creating your own story within the world. There is the whole "woo-hooing" bit, but it's under covers and is something you could probably tip-toe around.
 
EDIT: What platforms do you have, anyway?

You could give the newest Spiderman game a try... I haven't played it myself, so I don't know any details, but I've heard that the free-roaming stuff is pretty nice in that game.

 @FireBurger: Pokemon is definitely something that is likely to start in the house, he really wanted to get into it last time and now I think is literacy is finally up to snuff, he really tries to challenge himself, but that can often lead to frustration. He insisted on playing my Picross 3d the other day and about 2 puzzles in was a rather unhappy bunny indeed
...

" I have a little cousin who's around 7ish. I was at their house one day and he pulled me into the basement and booted up his gamecube. He handed me the controller and told me couldn't get past the first level.   He was playing Animal Crossing. "

If he liked LEGO Star Wars then LEGO Indiana Jones might be a good game for him.

You could try out Fable 2, but I don't know if that's too violent?

@aafie:

I'd put a second in for Super Mario Galaxy.

 a 6-year old son playing games like that sounds... rather... 
 
actually, i'm not a parent myself, and i played Duke Nukem 3D when i was 6. And honestly, i played DN not for the pixelized strippers nor the gun violence stuff... i actually enjoyed travelling through the levels exploring (even sometimes it gets real creepy, for example a supermarket's butcher section had limbs everywhere) So i guess that relates, why kids play games. I personally still enjoy visiting different worlds up to this day. I am sort of adventurous in real life too.  

 when kids are in that stage of  Initiative vs Guilt in Erikson's psychological development terms, i don't think it's too bad to try games that have a moral spectrum to them, or bring a rather more serious consequence if you violate the rules, with you monitoring. although i can't think of any at the top of my head, i bet there must be tweak to disable the blood in the pc version of fable I. Just make sure your son doesn't know there are decapitation moves. 
 
I would suggest bully when he gets older. Do not judge the game by its name. the game is about Bullying Bullies. and one thing that contributes to the point i was making before -- prefects and law enforcers in that game are almost unbeatable. If you do something wrong you get caught. You could argue that teaches the kids you can violate the rules, just don't violate them in front of people. So again, monitoring is key. and from what you've typed up so far, i trust you as a pretty responsible parent. (you could even learn more about his school life in the mean time, kill 2 birds with 1 stone)
 
btw, i hate peter molyneux for implementing such violence into a seemingly cartoonish styled game. I mean, it's not appealing to adult gamers like me (the bigfeet is dumb to me), nor can you really give such a game to kids. But anyways, worth a try.

oblivion on the pc may also work, because it's very tweakable so you could turn off the blood. if the oblivion gate sections get too scary (zombies, hanging corpses and torture stuff), it's always possible to install a mod that would skip that part of the game entirely.  it's a game i think i would enjoy if i were a kid. 
 
i would agree the gaming generation gap is there. Although i would say fallout 3, fable 2 is equally violent as duke nukem, dn was in pixels. Now with HD graphics it's hard to avoid violence. And honestly, we really are getting a lot less spyros and crash bandicoots these days. 
 
Anyhow, good luck. i'm glad to see parents who grew up gaming have such passion and responsibility.

" If he liked LEGO Star Wars then LEGO Indiana Jones might be a good game for him. "

 @aafie: oblivion can be played 3rd person but i agree it plays funny that way. The TOTALLY UNREALISTIC physics should be ok...
 
i would shy away from browser based stuff too. club penguin could be a good first try, but since these stuff are more chat than game, it is very very easy to fall prey to strangers, or simply get bad influence. i simply do not recommend having the weirdness of the internet seep into a child's mind well before being 16. (no joking)  
 

@FireBurger:

" @FireBurger: for six, he's pretty proficient. and I would be there beside him for any rough bits (whether puzzles or text) Well I have Twilight, so we'll give it a go. "

Depending on how you feel about guns and such, the Ratchet and Clank series may be a good option with plenty of content.  The entire series is practically based on guns but it's all cartoonish enough, coming from the same studio that made the original trio of Spyro games.
 
Jak and Daxter is also a really good choice to look into if he doesn't mind taking a step back to the PS2.  There is a minor element of collection but it is mostly based on Crash Bandicoot style combat and more open exploration.  The second and third iterations of the series are a little more gritty, and more open as well.  Kind of like a much more innocent and cartoonish Grand Theft Auto style game.  Also on the PS2, maybe have a look at the Sly Cooper series?
 
Little Big Planet would also be a no brainer as well, if you havn't already gotten into it.

I don't know, are the Monkey Island games his type of thing? Monkey Island SE is good fun, although it may be a bit complicated (though the hints system is pretty damn lenient).

Any Ratchet and Clank game is kid-friendly.  Halo, although rated M (18+?), is pretty cartoony and lacking in red, human-like blood.  Also, the vast majority of XBL Arcade games would be just fine for kids....oh and of course God of War, GTA, and Gears of War are just great for the little guys!