I had this idea to create histories for maps (small bits of history, not a huge storyline) and started it tonight. I decided to call this "Legends."
My idea is:
Create a fresh world and play for one life w/o using food (if you happen to get food in a dungeon, you earned it). Once you die, leave everything as is and go to where most of your activity took place and place a sign with a title for whatever event took place there. Then go make a text document with the same name as on the sign with the history/legend of what took place there. Now open MCedit and set a new spawn point elsewhere on the map, wait until dawn, suicide, and save the game. Now give a friend the save file, and have them do the same thing around this new spawn. Repeat this cycle with atleast 2 people. Keep in mind more people in this cycle means you wrote a smaller fraction of the history and therefore creates more adventure for you later. Once you're satisfied with how many legends you have created, host this map as a multiplayer server (hopefully you will be able to fight mobs before this) and build on it while exploring histories. Make sure everyone has a copy of all the legends (only read legends when you find the corresponding place).
Don't explore the histories you wrote. Leave them and the loot left behind for others to discover.
Create events or such in your histories. A treasure map to a chest of loot maybe.
Legends can be grand legends, or something less grand, like a diary of an unsuccessful coal miner.
You can attempt to create an overarching story, but cooperation with other players means there are no surprises awaiting you.
I finished my first life a little while ago and uploaded the files so my friend could start his turn. I think this could create a pretty cool map. My first legend left behind some pretty interesting items, and hinted at some secrets that hopefully someone will get to discover someday. Also, knowing you only have one life has an interesting effect on how I play. It seems I am more productive as I'm less worried about dying, because that's part of this whole plan.