If you draw your maps with only three palettes, you can use the fourth for battle whenever you need it. Or you could draw things out of sprites but always keep them synchronized to the map scrolling; Super Mario Bros. does this with Fire Flower powerups.

____________________
My English is better than your Geberquen.