Oh, this sounds like fun, and also similar to something I tested out for Tribes way back in the days of the old construction mod.
Procedural generation is reliant upon a tile set, or a list of objects from which the generator may select from. So, for your dungeon generator, you'll create a large number of tiles (Start with a small amount and branch out), including the following "bins":
- Starting Room
- Room (2 Doors, 1 Entry, 1 Exit)
- Room (3 Doors, 1 Entry, 2 Side Paths)
- Room (4 Doors, 1 Entry, 3 Side Paths)
- Connector (Hallways if you'd rather)
- Dead Ends
- Exit Room
The generator itself will be coded to place each of your tiles within one of the above "bins", then the fun part. You'll have the generator start by randomly selecting a starting room tile, then randomize the number of rooms to reach the end. From here, you'll establish a selection from the connector and room bins (Randomly selecting 2, 3 or 4). When it selects a room with multiple routes, it will have another random element to decide how far it will reach away from the "designated path", and then continue branching out. Once the end is reached, select a tile from the exit room and voila.
As for the tiles themselves, this will require a bit of work on both the script side and modelling side, which is why some good debugging techniques will be required here as you'll need to get the room sizes and scales down precisely as such the flow looks good.
For generation prior to loading in, just have this occur during the pre-game time frame, or if you need it during the active game time, just have the camera at a different location with a GUI element over the screen specifying the user to Please Wait.
Navigation meshes should make use of the Recast module that Daniel Buckmaster provided to the engine a while back, you can easily detect the size of your generated dungeon and stretch a mesh over it and have Recast generate nav points for your AI very easily that way.
It's no small task by any means, but I think it will be well worth it for your project in the long term to have something like this. Good luck!