Darklands was my first thought. It's sandboxy-open-world game. Quite a lot of people who played it didn't even realize that the game did have a main quest. It's, however, RPG game.

Endless Sky I suppose could be called an open world game. There's no story - you just kind of go wherever you want and do whatever you want. Pretty slow to get going though. Can take a while to accumulate the funds to buy a bigger ship.

Sunless Sea may also be considered open world, though most of that open world is nightmarish and absolutely unforgiving. Contains the best writing I've ever seen in a game.

Sacred has 3D character and monster models, but in a positively massive 2D world. However it's clearly an RPG.

Sid Meier's Pirates is a very good open world game, but of course its fully 3D. Perhaps the original Pirates game is worth checking out then

Cataclysm: DDA is an, I think, excellent open world survival game that I'm playing at the moment, that isn't that heavy on rpg elements. You do have skills and traits, but there's no character levels. Instead you get better by practicing/reading up on skills (e.g. melee/cutting weapons/first aid etc.), crafting better equipment, installing cybernetic modules and/or mutating into whatever you want (even a nightmarish spider creature if you so please)

I would recommend Dying Light, which is 3D and has RPG elements, but is still very different to Elder Scrolls and Zelda... It's actually a parkour (zombie apocalypse), crafting, melee action game... :-)

It might be helpful to narrow down what sort of gameplay are you looking for. I might suggest Factorio, but thats WAY different than any other open world game I can think of.

Roundabout, to a certain extent. Well, it does use a 3D engine, but it's not FP or over the shoulder chase cam. And the "world" is small, but it's open.

Also, the first two GTA games are 2D. And Retro City Rampage DX, although I haven't played long enough to know how open it really is. Not sure if Westerado: Double Barreled would count, too.

I am really looking for open-world games that are not what you would normally think of when hearing that term.

One example of an open world game that would fit what I am looking for is the original Zelda: Most of the world can be explored right at the start, and there is very little item gating (really only the raft and ladder are required to access certain areas). Also, it doesn't contain the RPG elements seen later in the series like towns, quests, dialog (other than very rudimentary dialog), crafting, and inventory management.

What I would really like, incidentally, would be an open world game that is a sidescrolling 2D platformer. Think something like the original Metroid here.

(Incidentally, the original Dragon Quest/Warrior is another game I could describe as open world; the only thing preventing you from just going to Rimuldur or Cantlin/Mercado right away is the strength of the enemies you encounter.)

Then I would suggest looking into Dust: An Elysian Tail.

Edit:
Oh wait. I cant remember if it has the item gating thing. Probably does.

Space Rangers
SPAZ 1 and 2 (2 more open-world than 1)

This is not a troll post, I mean this.
It is actually a lot like Metroid, save for the fact that the protagonist is a slacker instead of a famed intergalactic mercenary.

UnEpic

I have played Dust, and it doesn't qualify as open-world. In particular, the game consists of discrete chapters, and you have to play the chapters in order. To qualify as open world, you have to be able to go almost anywhere at the start of the game; Dust does not allow this.

I've also played Unepic, and the game, as it turns out, is also quite linear; you need to play through the earlier parts of the game in order to reach the later parts, and they have to be played in order. Hence, this game is not open world either.

Wow. I really do not remember that game at all then. My last suggestion is Terraria maybe? Its procedural, but im pretty sure the world is open. Haven't played it much myself, but people really love it.

The only ones I can think of that might qualify are Don't Starve and Sunless Sea. Don't Starve is a fun survival game with a randomised open-world and you can customise certain aspects of it like weather, which animals/enemies will spawn, size of the world map etc. Sunless Sea, as mentioned above is a very neatly crafted exploration game the kinda plays like a CRPG, with minimal RPG elements beyond the base stats and upgrading your ship and such. I prefer to play with the rogue-like mechanic off because I enjoy it so much more that way, but that's just me.

And if you don't mind a 3D open-world game suggestion, than I highly recommend Sleeping Dogs. It's honestly one of, if not, the best open-world game I've ever played. It kinda plays like an undercover cop/action/thriller movie, like a John Woo flick, and it has a pretty good story to go along with it. And the city is just so much fun to walk/drive around in and explore and the hand to hand combat is nice and satisfying. There's also some shooting and a slow-mo bullet time to go along with it which can be pretty neat. I just think it gets a lot of things nicely that I find other open-world crime/cop games tend to do an average job at. It's definitely worth taking a look at if that kind of thing piques your interest. Hope that helps! :)

Uncharted Waters: New Horizons has always stuck with me for some reason, but if you're looking for something Metroid-y, maybe Axiom Verge? I haven't played it and don't know about its open-ness, but remember it getting a lot of Metroid comparisons.

And yeah, I second Terraria, too.

If you don't mind metroidvania-puzzlers, give La-Mulana a shot. Highly non-linear, but there are eventual roadblocks concerning access to the "back", so you will have to start beating bosses or use a certain shortcut through the Tower of the Goddess. You can complete at least 2/5ths of the game before having to touch a boss.