To edit the palette, open the rom in fceux. Play until the screen displays the palette you want to edit. In the debugger menu, display the ppu viewer. The palette is displayed at the bottom. Each color is represented by a two-digit hex code. There are two rows of colors, each four sets of four. One row is for background. The other for sprites. The first color in each sprite set is displayed as transparent.
Write down the sequence of 4 color codes. Then in the debugger menu, view the hex editor. In the hex editor menu, change the display to "rom."
Use file search to find your sequence of hex codes. When it arrives, choose "find next" to ensure that the sequence only occurs once. If it occurs more than once, you will have to trial and error your way to find the correct one. (If it does not occur once, attempt the search without the first color. Often roms will establish the transparent color once and store the other three colors separately.
Type the new sequence over the old one. You can know the hex codes of the entire palette by doing a google image search for nes palette.
The changes will not take effect immediately. You will have to get to a point in the game where palette data is being loaded. In some games, you can pause and unpause. Some you will need to change levels, some older ones only do once upon startup, so you'll need to reset. (You know the palette data is being loaded if the colors in the ppu viewer refresh.
If your change is successful, select file, save in the hex editor window.
This may sound daunting if you've never edited hex before, but it's really very easy and a basic skill. Do it. Take a screen shot and post your results.