How difficult would this be? NEW GAME +

Creating a New Game+ is not conceptually difficult, but it would require a lot of event space and a crazy attention to detail. You would just need to clear every event bit that was set, and set every event bit that was cleared. You could do this through an event, and check to make sure that the 8 dragons have been beaten as a condition to start it. You would also use that event to un-recruit all of your party members.

It would probably be more economical, and less of a headache to write custom ASM that allows you to copy a block of values to RAM, kind of like how the game handles its initial event bits. (When you boot up the game, it has certain event bits already on or off before you even select "New Game". If you start a new game, it uses those bits. If you load from a save file, it overwrites those with what your save file has. You'd need to do something like that.)