Once the image is loaded by SOIL, it's stored locally and handed off to OpenGL's internal format. The original image format is irrelevant. You may think of what you're trying to do as optimization, but it's not. In the way-back days, graphics were displayed with pallets that could be edited. Now they're not. So you'd literally have to iterate through the pixels looking for ones to swap out. A shader would be the a way to do this, but perhaps not the best one for speed and compatibility purposes...
Now if you're doing this as a feature that you actually want, the way to do it would be (probably) to create multiple images at load time. Load the original, then in C++ code, make whatever mods you want and save each mod as a new image.
