I don´t know if there is a way. As far as i know (not read all Documentation) you cannot change the ID or to change the User connected to it.
Firebase is giving the ID back when a Devices registeres. Even in the Anonymous variant.
If a user then get a new Device then Firebase will probably create a new Id for this User.
You need to get rid of the new Id he got by yourself (your own Serversolution where you store them), Post it to your Cloud. On the Cloud (php, whatever) you can get this id and write the token to your database using the correct account. You now use the new token from this user...