Idea: Broadcast legends. If a certain - lets call them "named" or whatever - monster is generated, let the player be able to actively hunt it by spreading rumors through neighboring towns. The more dangerous the named mob, the farther the legend may travel (so that our puny hero has enough time to toughen up, hehe). It would be even cooler if those mobs wouldn't just be the usual suspects like black unicorns or dragons, but maybe even other adventurers.
Even more awesome idea: AI-controlled adventurers that could be rivals or even optional companions for the PC, doing what adventurers do, i.e. killing monsters, raiding dungeons and stuff. Imagine you enter a dungeon and see the first couple corpses. Is that a banshee level? *dread*... nope, just another adventurer was busy farming for exp and gear. Maybe even let them drop messages. "You pick up the crumpled scroll. You read the crumpled scroll. The crumpled scroll says "beerslayer was here". :)