Add the new account first. Then, as the AGOL Administrator, move the user's maps and items from their Old account to their New account via >Gear >Manage Items >Change Owner. Then delete the old account.
Can you explain why security reasons prevent the changing of the address?
I am an admin for our organization and as such am trusted to perform certain actions. Can changing the email address of a organizational user be one of those trusted actions? It is not uncommon for staff in my agency to have their email addresses changed (marital status change etc).