Well, I know I am not the only one to have the following philosophy, nor am I the one that has done it first or perhaps even best. There very well may be many quests that have done this before, but I will illustrate it anyway. So without further rambling...
...It's pretty basic, but as you can see, the portion of this test dungeon here looks pretty flexible. It has a fixed path, sure, but exploration is a little more interesting with a sense of progression and discovery at every turn. As you can see, the key (no pun intended) here is to abuse the hell out of keys, optional rooms and multiple locks. Now, I ain't saying there should be a key and locked door on every screen, but rather you should focus on using keys and doors to make flexible paths. The room with the chest is purely optional, but it's a part of the big picture nonetheless. You can access it with the very first key or the very last key, it doesn't matter as you get a spare key (and a chest) within at the cost of beating up some enemies or doing a puzzle.
Again, don't put a key and lock in every room. But rather space them out, and keep keys and locked doors (and optional rooms) as your tool to make a dungeon feel less linear and more complex.
tl;dr forget about making a dungeon screen by screen, shape the entire map. Do the walls and floors first, gameplay next and detail last. And let me tell you, no amount of scripting will make a dungeon feel this non-linear without resorting to feeling gimmicky.
Edit:
Your dungeon could also have a theme. I am not talking about the more conventional definition. I am talking about if your dungeon will focus more on combat, puzzles, exploration, etc. Will players being earning more progress by beating enemies or solving puzzles or finding secrets? It won't hurt to throw in a puzzle within a combat-based dungeon, but bashing up enemies, finding and exploiting weaknesses should be your primary goals within a combat-themed dungeon.
Of course, that leads to the dungeon item. You should foreshadow what the dungeon item all over the dungeon. If you have selected a theme, it should reflect such a theme. For example, let's say you have a ball and chain. You can now destroy armored enemies that were once impossible to kill, and access rooms they were guarding. That would work best for a combat-focused dungeon. Or now you have the magnet gloves, and now you can push or even pull blocks that were once far out of reach within a puzzle-based dungeon.
Edited by Shane, 25 March 2015 - 04:27 AM.