A simple solution is that when you are storing token of a user in your database then at the same time save the device's UUID as well which will identify that device. Now, if a user deletes the application and re-installs later then a new token will be sent to server from the same UUID. Detect that and update the old token.
Case 2 is that if user doesn't reinstall the app then would the token will remain save in DB?, to detect the application deletion a Receiver is implemented which detects event if user is upto delete the application (How can an app detect that it's going to be uninstalled?) . Inform your server about that event and disable that id.
Why I'm not asking for deletion?
The Receiver detects when user opens app deletion dialog. But what if user goes back and doesn't delete the app? in that case whenever user open's the application inform the server that app was not deleted. This thing could be handled by saving a boolean value in sharedPreferences.