I can't say I would recommend random level generation for a Metroid type game as all the back tracking and interesting hidden locations are what makes it interesting. It isn't the sort of thing random generation is good at.
That being said you would want to think of a level as a number of interconnected rooms. Usually with a hallway or ladder in-between. For each room randomly connect it to anoth