Quote:
In my view, dealing with the palette limitations on the NES is the one thing that most makes it an "NES game". I think it ends up making a big impact on every NES game's design, probably moreso than other limitations of the system.
I just quote you because I agree

Also the 8-sprites per line limitation make it difficult to overlay sprites without running into problems.
As for answering the original question, my opinion is that 1 palette for player 1, 1 palette for player 2 and 2 palettes for enemies is the very standard way to do it (assuming a 2-player co-op game). If you need the palette to change to reflect player's state there's not much else you can do. The only thing you can do is change the enemy's 2 palettes during the level.
Just Breed has a system where it loads the sprite palette dynamically in function of what it needs to draw, every frame. As far as I know this is unique. It also uses some sprite overlay for the hero, meaning the first 2 palettes are "fixed" and only the last 2 variable (dynamically loaded).
Another very simple "trick" is to have a constant sprite palette across the whole game. It might sound like it's not a very advanced technique, but it works wonders for
Castlevania and
Battletoads&Double Dragon for example. Since you know what colour palette you have at all times, you can reflect state changes of the player by changing them, and any enemy can use all 4 palettes freely.
Battletoads on the other hands has only the 4th palette which is variable.