If the user never entered credentials then he/she would not expect to recover an account. The user could contact the app company and they could do a manual account matching, maybe with other user data.

Or he could borrow an iOS device and log-in with his iCloud credentials.

Generally that is very unlikely scenario I guess but thanks for discovering that edge case!