The requirement of randomness is one of the big questions in roguelike development. How random you can or should get? When you look at a classic like Nethack you'll notice that it's not that random after all. The structure of the game world is quite static with designed locations that don't often change.
I've struggled with the same requirements myself. It's difficult to produce random content and still create something that's themed. Like level themes for locations in the dungeon. It looks like the best you can do is offer some random changes in the typical theme content. But you simply can't get too random in the context of the theme. Dry sand levels can't be populated with winter wolves or some other cold environment creatures, if you try to stay in theme based content.
Then again, does it have to be that random? Well, mainly it does. There are good examples of static content that quickly becomes tedious if you replay often. Something like the main "village" in Angband/Moria or Terinyo in ADOM. Maybe there could be couple of different starting points to reduce that kind of dull, repeating experience. Something like several entrances to the dungeon, each leading to different part at first. Or maybe you could sometimes start from deeper levels with better equipment, like in middle of the story.