I don't care much about destructable things atm, but as this thread gets longer I have some ideas too
Lets asume that the only destructable items will be human walls. It isn't a big concern, as if you shoot a rock, it hardly becomes destroyed (actual RPG and rocketlaunchers doesn't really breaks big natural rocks anyway). This allows the coders to only have to pay atention at walls (straight lines between point A and point B), forgeting rocks, trees and terrain that would be very difficult to code.
Now we put the "hardness" of the wall in the texture applied: it would be easier to asing an integer to the texture file (jpg or whatever, most of the formats used allow comments) than replace each map.
When the wall have to be destroyed (damage higher than "hardness" in the impact point), the wall splits in two, from A to impact point to B, and the height of that square can be lowered to the height of the floor in that level (eyecandy as rounding the borders can be applied later). Each destruction only adds few polygons as the human walls are basically boxes and rectangles.
To bring the processor time to compute the new map, we can add some easy visual effects (shake the camera, add some animation of smoke...).
Just my thoughts, and I really think that a consistent storyline is more important at this moment