First of all, I think its a really hard task you have in front of you, and thank god its not me <img src="smileys/smiley36.gif" border="0" align="middle" />
I haven't actually made any platform games, so not that much into that part and what problems are typical for them. But maybe I can give you some ideas to try, as all the games im working on, uses random generated maps. However this seems a lot more complicated, as I don't think I have the same limits as in a platform game.
Anyway ill just use a game as Mario as reference, since that's what you mentioned, so if your game is not like that, you can just ignore those parts.
To generate the map:
You need to take into account that the character can only jump so high, so you need to make sure that all objects that are part of the map are reachable. As it wouldn't make sense to place an object in the top, if there are no way for the player to reach it, or to place an object just out of jump range.
So what you could do, is to divide the whole map into a "hidden" grid of lets say 128x128 px tiles, lets say its a 10x10 map. Each grid tile could hold some sort of map object.
Now you need to fill the grid with map object, and think it would make sense to start from the bottom up.
Since the player shouldn't be able to fall off screen, you know that all the tiles in the bottom needs to solid. So you can add solid map objects to all of them.
Then you could go through row 2, and just make a random roll to see if there should be an map object in a given tile or not.
If you want to go higher, I think I you would have to make a tester of some sort, that would pick a tile and the surrounding 8 tiles. To see whether one is present or not in a given tile. To explain it a bit easier:
Lets assume that:
O = empty grid tile.
X = Map object.
T = Location of the tester
Tester looks like this, with the number to represent the tiles needed to be tested:
7 8 9
4 T 6
1 2 3
So if you want to test the tile marked with the T, to see whether you should/could add a map object here. It would look like this:
OOO
OTO
OXO
XXX
The tester will check the 8 tiles surrounding it, to see whether it can add an map object or not to its current position. Since the player can only jump 1 grid tile (128px). So testing the grid tile at position 1, should return "bad position" or something, as it doesn't have a map object, so placing a map object at T current position would make it look like this:
OOO
OXO
OXO
XXX
And impossible for the player to jump there.
Then you would go through each row of the grid and test each tile like that.
Spawning random monsters
Assuming that you made a tester as above you could use it to spawn random monsters as well. Either by marking tiles as "containing" a monster, and based on whatever conditions you want, make it so it can not spawn 2 monster on two tiles that are next to each other.
Anyway, think you could make it like that. But it would probably need a lot of extra work, as the maps might tend to be rather boring, the you could ofc add tiles that trigger something when the player is on them, but that will make it even more complicated....but think it will be very hard to make regardless. As I can only guess the amount of bugs it could create :D
But anyway maybe you can use it for something, if not its fine as well :D