If 233 tiles are used, then maybe the spare tiles can be used for the mutable tiles, depending on the number of mutable blocks.
A bridge, for example, could be allocated tile 255. There can also be a flag set or unset, depending on bridge visibility. When rendering, check the flag. If unset, render 'air', if set, render 'bridge'. Sure, this might only mean you can have 20-70 bridges, destructable blocks, etc, in a level, and I don't know if that's enough.
Also whilst you might want *all* the graphics, it may be prudent to selectively eradicate some that don't add value. But this is probably not going to gain much except reduce the tileset size (not a massive worry on a cart or multiload 128KB), and allow more mutable blocks. And possibly aid compressibility.
Another option is to analyse the level layout, and see if there are any 'bottlenecks' (single route between map areas) in the layout, where you can split a level into two or more levels. If the map is very open (like Turrican) this won't be an option.
And finally, if you are happy to do some map editing, instead of having 1 byte = 1 tile, consider 1 byte = 2x2 tiles (5KB level, not 20KB), and have a lookup table of those tiles. A common way to save map data on 8-bits. Also on a cart/multi-load 128KB the large level size isn't an issue, although nice to fit it into 16KB.