I've had a hunt around the forums and found a few things that look interesting...
dc443's sandbox (http://www.box2d.org/forum/viewtopic.php?f=6&t=975
) which is very cool but (unless I'm mistaken) was just a test for dc443's game, so doesn't come with source. I do like the way it lets you draw shapes and then break them though.
Nimodo's testbed sample (viewtopic.php?f=3&t=836
) which does the breakable thing with joints and has a constrained Delaunay Triangulator, which is something I'm very rusty on the details of but believe it to be quite a nifty way of breaking up shapes into usable polygons. The breakable joints look like they might be a bit flimsy for the purposes of simulation something that looks like solid but destructable terrain, but perhaps that could be tweaked.
ewjordan's thing here (viewtopic.php?f=4&t=83
), which I'll admit had me completely confused in the thread but looks like it might perform some kind of preprocessing step to generate usable geometry, which could presumably then be made to be breakable at runtime.
I'm not sure which (if any) of these were the kind of thing you're talking about, but I kinda understand from looking at them the kind of thing you mean by convex decomposition, and what it can do - although I haven't looked up how the algorithms actually work in any great depth.
So, what I'm currently thinking about is constructing a level where the static geometry is formed from a number of relatively large polygon shapes, and when something happens that could damage the terrain, find out which shapes would be affected, and perhaps carve them up into a number of smaller ones, some of which can be made dynamic (i.e the debris chunks which are blown out of the terrain - possibly these would just be used for cool visual effects and could be removed from the simulation entirely after a short time), and some of which might remain static so that the visual effect isn't one of a big triangular hole. Am I thinking along the right lines now, or am I still way out?