You could do the sides with sprites, and clearing the characters at the right time, as you have said.
But the top and bottom, I would use something more like raster bars to do the top and bottom.
I would first prepare a tileset which is all blank, so that the characters won't show.
Then, when I get to the right scanline, (the one I want to cut off at the bottom that is), I would just set the background colour to be the same as the border, and also point the character map to this "invisible tileset". And obviously set the colour and characters back up again where you want to characters to show, at the top. I think this is the fastest way. It'll leave enough time for you to do your decrunch or precalcs or whatever.