I think that there are very few such users, and it will be easier to do it all manually, but I will still describe what I mean.
- The player on a special page submits a request, which contains the email and Mojang nickname.
- The service sends to email a skin that is generated randomly (it is not selected from the library, it is generated).
- The player installs the skin into their Mojang account and returns to the service to check if the skin is installed correctly.
- If the skin is installed, it allows you to continue registration with this nickname. The player who previously had this account receives a letter stating that his nickname has been transferred to the ownership of the Mojang player.