I would have thought the solution is simple - release an extremely primitive Android app of the same name and splash screen that says "Coming soon", and report back to Apple "Yes, I have an Android version of my app."