Remember, Procedural-Death-Whatever's don't have to be top-down, turn-based, dungeon crawlers! If you want to make a platformer with procedural generation and permadeath, that's great too!

Here's some resources of my own:
http://opengameart.org/content/super-miyamoto
http://opengameart.org/content/super-miyamoto-land-tilesets

From a long-abandoned Mario clone game, starring Shigeru Miyamoto!