Yep. That’s what a couple of plugins do, including
Colormap. There’s even a LED-Palette-Theme plugin that aims making this a little bit easier. Mind you, that one pretty much depends on EEPROM. But a similar idea can be made for RAM- or PROGMEM-based palettes too.
So yep, entirely plausible!