> changing the palette will affect all pixel of that color

Not necessarily, because same color doesn't require same palette index. If you are going to preprocess the image anyway, you can assign one palette index to each connected component.