A bit of a thought experiment I'm trying to develop further has hit a stumbling block. The basic premise goes like this.
All of humanity one day wakes up to the entire world having been changed drastically on them. Important to this plot, all humans maintain the knowledge of the world as it had been with no obvious changes to memory. Changes, however are vast.
Everyone's appearance has changed in some way, some more drastic than others. An approximate 30% are even different genders than they started out as. Everyone's position has changed at least some, but most are still within the boundaries of their geographic location (see country). Rare cases may include people now halfway across the world.
History and all documentation appears to have been changed as well. Your new body has a new name and a new history to it. All documentation, physical media, internet and any other source you can think of has been changed to reflect this new identity. There is no proof, except in your mind, of who you had been and most of the people you had known are now scattered randomly dealing with the exact same problem.
Now, this makes for a really compelling start to storytelling and I really like it, but I've hit a bit of a stumbling block. The basic premise makes it almost entirely likely that the "new" leaders of countries are completely unqualified and no one would listen to them anyway. To prevent this turning into a post apocalyptic story we need to have a way to quickly return to a semi-stable government across the world. In order to accomplish that, at the very least, we would need some way for our existing leaders to prove who they are and establish themselves. Bonus points for a solution that don't allow every single person to easily return to their previous lives without much drama, but still prevent global collapse (if that's at all possible).
What is the easiest/fastest way for our leaders to definitively prove themselves without any physical proof?