допустим, но он все также должен быть идемпотентный между установками приложения, чтобы отслеживать одного и того же пользователя
Не должен на самом деле... вернее, не может физически, если кто-то хочет это похачить - он похачит.
Ну есть, как бы это сказать, легальные способы это получить... типа advertising id у Apple, но опять же, заинтересованный в смене этой штуки пользователь - сменит. Там в требовании есть очевидная вещь - "sign up" и вот это и является привязкой. Т.е. ты создаешь аккаунт... если надо незаметно детектить, что два ползователя - это на самом деле один и тот же девайс, то это тоже можно делать (но приближенно).
Делать это достоверно на 100% можно только на подконтрольном девайсе типа MDM.