Master Reboot - http://www.walesinteractive.com/#!master-reboot/c1vts

While it's a much better game than the reviews made it to be imho, and there's indeed no combat to speak of, there's really only one "choice" that you can make in the entire game, and even that one is debatable.

I've tried to come up with suggestions myself, but found it surprisingly hard.

Alter Ego! (The old 8-Bit one) - now available in your browser!

http://www.playalterego.com/

I don't fully agree with this one, there are "some" choices you can make, but most choices lead to your untimely demise and can't really be considered choices. I think if you want to finish themg ame, the path is actually quite clearly set out for you.
Unless you consider jumping in a pit is considered a choice in Super Mario Beos, in which case that game should also be added here considering how many pits there are to choose from for a little plumber splatter.

Heh - today's release - Consortium seems to fit your criteria (combat sounds optional, at least) what a co-incidence!
http://www.gog.com/game/consortium_the_master_edition

"The story unfolds based largely on your actions. You may use diplomacy and talk your way through the entire game - never shooting anyone! OR, decide to use deadly or non-lethal force."

Haha, yeah, those were my initial experiences with the game and I would have been lost without the help of my brother. He on the other hand apparently used his knowledge of the original Robin Hood story to get a decent idea of what kind of stuff you have to do and in which order, combined with a lot of patience and trial & error.

Dreamfall: the Longest Journey is like that. There's some combat and several sneaking sections, but they're marginal and don't detract from the overall storyline. The influence on the story is minimal, but there are still decisions to make.

Myst URU. It might help to play some of the previous titles first, but Uru takes place when the damage has already been done, and any antagonist is long dead.

Yeah, it looks awesome! Watched some gameplay vids, I don't think I want to spend $12 on it. Also, I read it's only 4-5 hours long.

Majesty 2 don't really have non-linear storytelling, you can only pick from several not connected missions, while you complete all of them anyway and there is a combat. A lot of it. Your heroes fight constantly.
So I don't think it fits your criteria.

Yeah, I realised that when I saw it in that 'One Day Games' thread still looks really good for what it is but £12 for that length?

Kind of like the first then? Are the higher level missions also nearly impossible as in the first game? It really seemed like the odds were impossibly stacked against you in certain missions.

Well kinda. I like Majesty 1 much more, but yes, the how the game play is similar. I only think the the 2 is made worse with prettier graphics.
I find it quite easier but I played a lot of 1 before. I know some people said it is too difficult, but I don't think so and it is nowhere as difficult as Majesty 1. There I had a lot of troubles with some missions and one of them I wasn't able to finish without gambling save scumming to get tons of money.
I didn't have similar troubles in Majesty 2, but some later missions can be quite hard but nowhere as hard as in first one. If you find what places to avoid to not trigger some monsters or scripts and if you know what will come, it will become fairly simpler.

Might give it a go then sometime, but yeah I agree, I prefer the look of the first game. The 3D graphics in Majesty 2 seems a bit 'generic' :P

King of Dragon Pass here on GOG is kinda like that.
It has a very open and always interesting story. There is combat but it is only a small part of the gameplay.
It is quite simple graphically speaking but it has wonderful images and art.