Is it possible to procedurally generate stable structures out of rigidbody objects at a reasonable runtime speed? Imagine Angry Birds's levels kind of structures but generated procedurally.
Of course it can be, but it won't be easy. Look at Spore by EA, they did it in 3D, and their level of freedom in designing your creatures there is amazing, and your creations there are complex simulated living organisms. What you want is something much simpler. What you will need is a validation system to follow a set of rules. You can't just go off randomly throwing objects on top of each other. Otherwise most of your procedurally generated structures will tumble down once they the physics engine kicks in. Good luck.
I think the crucial part of this question is how you can procedurally generate stable structures (as generating an unstable pile of blocks in real time should be no problem)
My approach would be to prebuild sub structures that are guaranteed to be stable. Have each substructure store two sets of spans" * one for the bottom where it requires contact below it. * one for the top where it has stable sections that can support sub structures above it.
I'd start with subsections that have perfectly level spans and get that working first, then you could add information to each subsection for the amount of slope it can tolerate below it. (this might be pretty tricky as the center of mass changes the way the structure below will deal with the lateral force of friction)
It's worth noting that this method doesn't support some types of stable block piles. All of the sub structures need to be stable on their own. (i.e. you couldn't have a structure that requires a heavy structure above it to hold down some off balance lever)
After that is working you could probably layer on some more sophisticated stability analysis to handle the more exotic substructure types.
Matching up the contact patches exactly will be a key part of making these structures stand up - tiny gaps or interpenetration will cause real problems. It will also help to make sure that the rigid bodies are created already "asleep".