You'd break everything, but it's possible to do it if you're doing a total conversion mod that loads a different asset file instead of srb2.srb.
THINGS YOU NEED TO REPLACE TO GET THE GAME TO RECOGNISE THE PALETTE:
* the "PLAYPAL" lump. simplest to do, SLADE lets you convert .png files into PLAYPALs
* the "COLORMAP" lump. also very simple. convert an image 34 pixels tall by 256 pixels wide into a flat
* the "TRANS01" to "TRANS09" lumps. also flats, 256*256.
THINGS YOU NEED TO REPLACE TO PLAY THE GAME WITH THE NEW PALETTE:
* everything else that isn't a map, text file or sound
* yes, this includes the .exe, sorry
* no, we're not going to help you make .exe's that do new palette stuff, we've got better things to worry about