Advance Sprite Palettes

Try searching the GBA ROM file for this combination of  bytes in a hex editor.

Code:

02 01 04 04 00 00 00 03

That's the list of palette ids for the first 8 characters. I found it in 2 places in the US GBA ROM. Try replacing index 4 and 5 (the first two zeroes) with the palette id you want for Edgar and Sabin. I think it should be 01 to get the brown soldier. That should change the palette that is used in battle. I might be able to add this to FF6Tools, but in the mean time it's pretty easy with a hex editor.

You can also search for this in a save state or sram file. I think it's stored in the same order, even for a GBA save state. That should change the palette used in the field and menu without having to start a new game. Note that this is in addition to changing the event script as Gi Nattak explained. In the US GBA ROM, Edgar and Sabin's palettes get set at 0x7A66B2 and 0x7A6D21, respectively. You can change these with a hex editor or with the event editor in FF6Tools.

Another thing, and this is going to be a lot of work, Edgar and Sabin often show up on maps as NPCs. The palette and graphics id for NPCs are stored differently from characters. This is how e.g. Gerad has a different palette from Edgar. This means you would need to go through map by map and change the palette and graphics of every Edgar or Sabin NPC you find. You can do this with FF6Tools. I would recommend doing this on a fresh ROM and then creating an IPS patch to copy the changes to a modified ROM. That way if you screw anything else up in your modified ROM later you won't need to do it all over again. On the other hand, if you later insert or remove any NPCs your IPS patch won't work properly any more.