There are 4 palettes for sprites, each palette has 3 colors + 1 transparent. You can't add 5th palette, you can only change those 12 colors. And you also can choose which one of these 4 palettes a sprite will be using.
Sprites memory is located in ram, it's a 256 bytes area, usually at $0200—$02FF. Each sprite reserves 4 addresses for its data, palette number is stored in a 3rd one by using bit0 and bit1. More info here https://wiki.nesdev.com/w/index.php/PPU_OAM
So you need to find where your wanted sprite's data is currently located in this memory. You can freeze bytes and/or overwrite them manually with a slow emulation speed to notice changes on the screen.
Now comes the hard part. Set a write breakpoint to the 3rd address and trace where this byte is taken from. This requires basic nes assembly knowledge and debugging experience. Change this byte to another when you find it.