Mirrors of $3F00-$3F1F could be used for the extra palettes. The only problem is that this would break existing games that use these mirrors, but maybe this could be something you could turn on and off.
I know that something like this will hardly come to life, since nobody would want to develop games exclusively for modded consoles, so this feature would be used exclusively for enhancements at best, but I can't help considering the kinds of improvements that could be done to the video capabilities of the NES without replacing the PPU altogether, even though this is much more invasive than something that could be put in a mapper.
EDIT: Another obvious enhancement is this area would be to use all 8 bits of the color values, allowing for a total of 256 colors to pick from, instead of the usual 54ish. Sure, this too would break compatibility with old games, so it would be ideal if these features could be enabled by the software.
EDIT 2: Please ignore the striked out text, it was just me not thinking clearly. I also want to say that I don't think these kinds of hardware modifications are necessary at all, the NES is the NES and I love it that way, but some times it's fun to consider the possibilities.