The texture data editing method discussed here will definitely work. If you plan to change palettes on the fly, depending on how many textures you have, it could be a little expensive. The shader method is a little more run-time expensive. You'll have to decide what's right for you.
If you're looking for an example of a method using shaders, here's some similar discussion...
In that thread, the goal was to replace a greyscale palette with a coloured palette, so it's not quite the same as what you're after here. However, you could always use the R, G, B, or A value of a pixel in a reference index to a palette that is supplied to the shader via another texture (or array of float4), which would simply the shader logic considerably.
I used to code a lot back in the day using QBasic and you can have a lot of fun with an indexed palette