How to get Android to store app data in user's Google account so it is restored on-install on new devices

Question

We're implementing a loginless system on our web, iOS, and Android app that allows the user to have a persistent identity without requiring any sign-up/sign-in flows whatsoever.

A key part of loginless is relying on iOS and Android to permanently store our app's data in the user's iCloud / Google account so that the data is automatically restored for the user in each of the scenarios:

• (i) Quitting and re-opening the app (accomplished with SharedPreferences in Android, UserDefaults in iOS)
• (ii) Uninstalling and re-installing the app on the same device (accomplished with key/value backup in Android¹, Keychain + NSUbiquitousKeyValueStore in iOS)
• (iii) Setting up a new device based on a backup of an old device (accomplished with key/value backup in Android¹, UserDefaults + Keychain + NSUbiquitousKeyValueStore in iOS)
• (iv) Installing the app on a brand new device signed into the same iCloud / Google account that the user previously used the app with (accomplished with NSUbiquitousKeyValueStore in iOS)

The only case we have remaining is figuring out how to accomplish (iv) for Android. Does key/value backup in Android restore the data in this case, even when the brand new device wasn't set up from a backup of an older device?

We've discovered the existence of Cloud Firestore and AccountManager during our research, but it seems like the data in Cloud Firestore is keyed on an device basis so it wouldn't accomplish (iv), and it seems like AccountManager requires asking permission from the user to ask for their accounts via android.permission.GET_ACCOUNTS, plus the whole design of loginless is intended not to ask the user for any personally identifiable information. Are we correct in these conclusions, or could Cloud Firestore be used to accomplish (iv)? Is there anything else we can use to accomplish (iv) in Android?

¹ We decided to use key/value backup instead of auto backup because the frequency of backups is greater than that of auto backups. See more information on the difference in Android's documentation.

Answer 1

Regarding the IV point, previous to 2018 you could use the now-depracted Android Drive Api, but currently you can use the Drive API v3 to enable an app to use the customer space in their drive to store application-specific data.

This folder is only accessible by your application 
and its contents are hidden from the user and from other Drive apps.

Answer 2

Shared preferences should restore from the previous device if the android:allowBackup attribute is set to true. As far as I know this works if you have your phone backed up at Google (Drive).