One layer of overlapping semitransparent sprites might actually do the job - you can have these in another layer in the tilemap. Rebuilding the tilemap should happen in a decent amount of time, as you won't have physics on that layer.
The only issue you'll have is the line on the edge - you could do that with the tilemap too - just have the permutations stored in the tiles, and when deleting tiles, pick the appropriate one to draw the outline.