A great idea (I'm sure I suggested this some years ago but no one understood me)

more texture memory use if everyone's the same character on different colors
Think in terms of worst case scenario: your best FPS doesn't matter, it's your worst that defines the perception.
In this case, worst case is when every player uses a unique skin.
There is no difference between that and different palettes.
P.S. Just quoting that book about making Quake, AFAIR it was like "no one will care if your best FPS is 60 if your worst FPS is 15, it's better to use a solution that gives constant 30 fps" or something like that.
P.P.S. No one uses palettes nowadays

When I'd
finally tear out of the bog of routine stuff, the
first thing I will implement in my engine would be palettes. Built right into the basic GLSL fragment program

Having this involved with team skins would be a waste.
On the other hand, IF your basic skins are B&W (dark trousers light shirt / light trousers dark shirt / checkered / striped / swirly AND you slap palette swapping on top of that, you get tons of unique variants, with most players looking unique.
It's like 2 dimensions multiplying, if you have like 5 patterns x 5 palettes you already get 25 unique variants.
And making patterns could be relatively quick and dirty.
Would even work with team skins IF you allow to vary palette colors inside a certain gamut (yellow/orange/red for the red team, cyan/blue/purple for the blue team)