Kicking out Umaro + Moogle Bonanza

Don't feel too bad, I'm tired and probably not explaining anything in a remotely close to efficient manner.
That being said, I wouldn't say "difficult" to replace Gau in the WoR, IF what I said actually works that late in the game, then it would be fairly simple by some standards. Event editing, yes, rocket science + calculus, no. It would be pretty cool to pull off though.

As far as Terra and Celes, you COULD have Celes replace Terra in that first battle with Phunbaba (starts around CC/49C1 in the Event Script). Just swap a few bytes that say put Actor 00 (Terra) in, with Actor 06 (Celes). Then you let the battle play out as normal, some event editing afterwards to make sure she doesn't come back. Remove Celes from the party, uncheck her "available" bit (which is $2F6).Terra would still be alive to recruit when normally able. Create the NPC you want to recruit to replace her. Have that new event check if Celes's available bit is clear (meaning she's been killed). Do the same steps as I mentioned before(this depending on if that works correctly), and reset her available bit after you've mutated her into your new character.

The only issue in the above scenario would be needing a check somewhere that made sure Celes wasn't the only party member, or just forcing it to put someone like Setzer in the party after that event so you don't end up with a party and no characters when you kill Celes.

I'll be honest, there are probably much more simple ways of doing all this... in my mind this just seems the cleanest as far as a stable/believable game would go. But yes, it requires event editing if you want to make it proper like.

The links I was given to learn from:

All Things Event Hacking
Good stuff to start with, even more good stuff once you've got an idea of what your doing.

xJCSx Event Editing Tutorial Videos
I'm not a video tutorial kinda person, but this page is highly recommended from alot of people as the best video learning you'll find on the overall subject.

And my personal favorite method? Dive in and see how much crap you can break... okay probably best to ignore that advice, but it don't hurt as long as you keep good backups.