not feasable. the palette colours are provided by the graphics hardware (although nowadays more commonly by a bit of code copying it out to the actual framebuffer later...). meaning you can't have some pixels using one palette and others using a different one.
you still need to change *all* the code to throw true-colour values at the screen.
fte's software renderer was 32bit. 24bit colour depth, but 32bit. hurrah for padding. noone uses actual 24bit framebuffers due to alignment issues.
updating code to use a truecolour framebuffer can at least be done gradually. code that isn't updated yet will merely draw to the wrong part of the screen, its not a problem until you want to take promo screenshots.

even if your source texture remains 8bit, you will likely want to make sure that your surfacecache is truecolour too. then your rasterizing code can just copy ints instead of bytes to the screen.
.