* Bulkheads. The map is composed of a bunch of small square rooms with automatic doors between them. When you enter a room, doors to adjacent rooms open; when you leave a room, doors in the previous room shut. It should be clear which rooms connect to which to make traveling less painful.
* Boat. The player is placed on a 3x3 platform in the middle of a large body of liquid (water, lava, acetone, whatever). Depending on where the player stands on the platform, the boat moves. The speed of the boat is presumably independent of the speed of the player, and could be fast, slow, erratic, etc.
* Modular vault. We make a whole bunch of mini-vaults with defined shapes and edges, and the game pieces them together like a jigsaw puzzle. Could easily be combined with the "bulkheads" approach.
* Giant tree. Passageways are large branches, with open space between them that can be seen through but not passed/dug through. "Rooms" are relatively wider spots where two branches are close enough to pass from one to the other; such intersections would be somewhat rare. Flying units could "walk" through open space, of course.
* Giant vault. An entire dungeon that's one huge vault with staircases between levels; basically a sequence of fixed levels.
* Moving walls. The dungeon periodically generates new corridors and removes old ones. The player must be certain to be in a room when this happens!
* Giant sandworms. The dungeon is continually being carved out by massive creatures digging through the sand, which then falls in a short distance behind them. The player must stay close behind the creatures, or have some special way to move through the sand themselves. Killing the sandworms is of course not recommended.
* Mixed type. This is a general concept -- just mix several different algorithms together. Partition the level up and use separate algorithms for each, so you could get a level where half of it is an arena level and the other half an ocean, for example.
The trick with alternate dungeon rules is finding a system that's interesting to play instead of being annoying. For example, I've found that trying to travel through FAangband's natural corridors is a bit annoying: since they're wide and irregularly-shaped, the "run" command doesn't work very well.