Helfen da eventuell die SharedPreferences weiter? Ich meine, die bleiben auch nach Deinstallation der App bestehen (bin mir aber nicht sicher):
https://developer.android.com/refere...eferences.html
Ansonsten wäre vielleicht noch eine Möglichkeit die IMEI, sofern man an die rankommt?