What we need is the ability to specify what order tiles slated for removal will be removed in. That in itself would clear up a lot of trouble and it would give a jumping-off point for new AI code to prevent the specific phenonenon being discussed here.
I don't see why we should go through the extra-tedious and boring job of manually designating the order of tile removal, when determining that kind of order is something computers are actually very good at. I'd rather have Toady automatize it than code yet another UI feature for this.
The basic idea would be to use a flood-fill algorithm every time a channel or floor removal is designated, to identify the whole contiguous region of tiles to remove. Then, treat the connected region as a graph where each tile has 0 to 8 neighbours, and apply an algorithm to turn that into a tree (the algo would either be another flood fill but from a tile on the edge of the region, or something more fancy from graph theory).
Once the tree is computed, a dwarf can only remove a tile if it doesn't have children in the tree, and it can only remove it by standing on it's parent tile. This should void cave-ins and allow several dwarves to work together without sending each other plummeting to their death. Performance-wise, the worst that could happen is a slight slowdown when designating if you designate half the map for channeling, but it shouldn't otherwise affect your fps.
This method could also be used for constructing walls in a smart order without dwarves locking themselves in, etc.