Android applications do not require Linux to work.* They do however require an Android runtime.
* unless they do, but that's another story.
BlackBerry 10 devices (which are based on the QNX microkernel) can run Android applications and I do not think they are running a full-blown Android operating system with its Linux kernel inside a VM on their phones to do that. Another, less pertinent example here would be the original ARC for Chromebooks, even if it turned out to be a technological dead-end. Alternative Android implementations do appear to exist too (Dalvik Turbo) but I do not know anything about them and especially if they require Linux.
I'm not suggesting this is something easy to do (far from it), but it's been done before and Google has the resources to make it happen once Fuchsia is ready for it.