I'd probably go with a set of hardcoded basic configurations which define where the exits are and which links to which (in the linked picture it'd be a T junction). Then you'd generate a whole map of these screens which link together properly. Once you've got that you can start adding more randomness and variety into each screen individually - making the exits bigger or smaller, adding in extra obstacles and enemies to make each screen unique.

The original zelda used a simple maze structure for it's levels, but the maze granularity was not tile-sized, it was room-sized. Each room was a cell in the maze, and each room was again it's own mini-challenge.

I would start with a maze generator that used a distinction between nodes and edges - that is, NOT one of the maze generators that fills cells either walkable or not, but one that marks cells as connected or not.

To account for things like locks and keys, generate multiple mazes and then make them overlap. The first maze is from the dungeon entrance to a key. The second maze is from the key to an interesting point (like the compass, or map, or the big treasure, etc) and it should overlap the first maze somewhat but not completely. Wherever it doesn't overlap the first maze is where you put the key door.

After you have several mazes generated and partially overlapping, you can find empty spots on the map and add secret rooms, or you can find two rooms that aren't connected and are far apart (judged by the shortest path from one to the other) and make a secret door between them.

Pick a very few doors randomly to make into one-way doors. Use path finding to make sure you don't completely block off a room (make sure there is some path to the room on each side of the one-way door). You might want to add exits to secret rooms that are one-way, so that bombing into them gives you a reward and then lets you exit to someplace later in the dungeon but doesn't give you a two-way shortcut.

Pick some doors to make into the doors that only open when the room is cleared, and use path-finding to find which of the rooms connected to the door is easier to get to and mark that room as one that should be a challenging fight (no reason to put that kind of door there, otherwise).

As far as making each room interesting on it's own, there three basic properties of rooms: amount of movement restriction, level of monsters, and number of monsters. Some rooms have long lines of blocks, or patterns that make it hard to move much, some have only a block or two that makes moving very easy. Some have tough monsters, some have weak monsters. Some have lots, some have few. Then there are dungeon themes like the one where there are dark rooms, and sometimes the obstacles are different (solid blocks, water, fire, etc).

There are also special occasions where the obstacles completely divide a room in half, so that even though there are several doors, you can't get from some doors to certain other ones, so that could be a special situation where very rarely, a room is split into two nodes in the graph. You might want to do that before the maze generation so it will take the split into account, or you could do it afterward by combining some parts of the maze so that two rooms with opposite doors (such as up and left vs right and down) are combined into one room with a divider, or you might randomly add a door and then block it off (like put a 'U' shape around a top door) just to grant a window into later parts of the dungeon.

The overworld can be generated using the same principles, except that you have far more secrets, and it is much more common for there to be a wall between some exits, and it is possible to generate the maze using tile granularity instead of room/screen granularity. In the original game, it seems the world was made mostly on the screen scale and then small tile-granular mazes were embedded at various points that ignored screen boundaries.