> but there's no state possible where the user can use the app and _not_ have given permission, as the app is only installable if the user gives access to the photos through the Android access rights at install time

Use an iPhone.