Hm, there could be XP gain increase at more difficult levels. Nightmare can feature random monster generation during the game (this can replace respawn, as it's easier to implement).
Will there be ASCII art for different Marine faces-difficulty levels in the beginning :)? Or was it Wolfenstein-only feature?..
How about progressive difficult, like in Max Payne (yeah, yeah, undoomish; just considering the options)? The better you perform (less turns, more monsters killed, less damage taken), the more difficulty raises, and if you do poor, it decreases. Not necessarily Difficulty Levels changing, bu certain variables can be adjusted - like monster generation rate, ammo\supply generation rate...