I while ago I saw a player w/ both cat ears and spiky hair equipped. Since there both classes as hair as they can birth be colored, wouldn't one have to override another one?

Yeah,it's possible to do so
You can put both in an empty set in ur deactive inv,then activate the set
And profit

I think its because cat ears is a 3d item and other one is hair.

Put a hair item in a set then activate it, while the other hair is inactive just place it in to the active set

That are both 'paintable' so I don't understand how that is the case

Both these items are hairs.
Way The7thVoid suggested will work, it's always the same if you want to have 2 hairstyles activated.