Y'know, I've been dabbling with palette modification myself.
Later Somewhere Doomguy meets the Hampsterbus!
I thought I'll make a new palette. I thought I should start with simple colors first. It should help me decide what colors to use. I've kept the colors in it semi-close to the colors in the Doom palette.
Here's the previous level, and low res textures with this low color palette.. I think the textures fit better together in this.. Kind of makes me want to do this in this style.
I was considering using a 6-8-5 breakdown of red, green and blue levels - that is, you have 6 levels of red (going up roughly 42.5 in value each level), 8 of green (going up 32) and 5 of blue (going up 51). More for green, because the eye's the most sensitive to changes in that channel, and less for blue, because that's the channel the eye's the least sensitive to changes in. This would create a 240-entry selection of colors that more or less approximates all possible color combinations, while leaving me 16 spare spots to handle grays (since multiples of 42.5, 32 and 51 don't line up much, meaning that I'd otherwise be using a lot of nearly-gray blues and yellows to approximate an actual gray).
I haven't actually tried using that palette in-game to any length, though; kinda curious as to how well, or poorly, it'd work. Obviously it'd absolutely wreck existing art assets designed for other palettes; I'm more interested in how it'd work for art assets explicitly designed with that palette in mind (or at least how it'd work if I took all the assets from an IWAD, converted them to true color PNG, and then tried them out in ZDoom with the new palette). Just trying out converting truecolor images to the palette in Photoshop, though, it looks pretty decent.
Translations would be a bit of a bitch, though, which is definitely a strength of the traditional "choose a color and do multiple shades of it" approach most games use.