How difficult would this be? NEW GAME +

That's exactly what the New Game + patch does (by Master ZED, who afaik hasn't been around the scene for many years), it clears/sets all the appropriate event bits and allows the player to keep most of the character stats, spells/Espers and items via assembly, not manually by event code; though it does of course do a small event edit for that NPC to add a normally unused bit in order to trigger the actual NG+ assembly code stuff, see further down for more on that.

Anyways, It'd be simple enough to just rework that NPC event code to add another 'if' condition of having defeated all the dragons first before branching to the NG+ branch, instead of just the 'we are in the WoR' check, like how it is. I wound up doing this same thing of sorts, editing the condition so that the player needs a certain Rare item (which are also handled by event bits) to trigger it. It's simple, but one would need to have a bit of hex editing and event editing know-how, but not much! FF6Tools could handle it as well I'd imagine, ROM-willing.

The only issue here is that there is no preexisting event bit for 'all 8 dragons have been defeated', because that's handled in a more complex way, so one would have to slip in/set another unused event bit for when the game gives the player Crusader, after defeating them all, then use that for the new 'if' condition for the NPC. So it would read: IF our new event bit is set from having defeating all the dragons & getting Crusader, then branch to the New Game + prompt... otherwise, do something else that comes after that check or just end the event.

The NG+ NPCs' event code changes are few - ZED basically just alters the 'we are in the WoR' branch offset in order to add a normally unused event bit ($066) which he utilizes for the NG+ code, so when that gets read after selecting "Yes", it does the assembly magic which is handled elsewhere.

Another glaring issue with this patch is that it will destroy FF3usME's dialog editor... I can't remember how exactly I got around that, other than probably dissecting the patch via an IPS patch report and making sure the dialog editing stuff is excluded.

EDIT: To make it even easier, one could just swap that NPCs' preexisting 'is in the WoR' ($0A4) bit check at CC/339C for our new bit we set after defeating the 8 dragons/receiving Crusader, or what have you. This way one could avoid adding on another bit check all together. Though, this would make it so that NPC says the same thing he does in the WoB, at least up until defeating the dragons. So it'd be slightly watered-down, but just as effective.