I don't think that pixel shaders help there (but maybe I'm wrong).
I know, there are instruction(s) for texture lookup operations, but, what if bilinear interpolation is applied to the texture?
So that, there is a 256x1 texture containig the palette itself, and there is a texture in some kind of textureformat containing the palette index values in one of its components. And then, using the pixels of the "paletted" texture as direct positions in the "palette" texture would work, I think. But, if bilinear filtering is on, then the interpolation would be applied on the palette indices themself, not on the lookup values from the "palette" texture. There are problems with the order of operations.
(Or, you should read all of the 4 pixels "rounding" a given position, then make a lookup for all of them, and then do the interpolation "by hand". Could it be done in a pixel shader at an acceptable speed? It seems very complitated to me.)