Android - Is it possible to run Android applications on (normal) Linux?
Nothing like that exists yet since the apps are not run natively in the OS, but they use Dalvik Virtual Machine instead (Wikipedia). It's somewhat comparable to Java in the sense that it uses bytecode and creates a separated environment for each app. So unless the Dalvik environment is ported to other platforms, they can't be run on normal hardware.
There is a project called Alien Dalvik by Myriad that tries to run Android apps in different environments, but there's not much info on it. Myriad Alien Dalvik
Things have changed a little bit in the years since this was posted.
There are now several (though none of them perfect yet) ways to run Android apps on Linux without an emulator or VM.
- Shashlik features pretty nice integration with your GNU desktop environment. Lacks Google Play Services, though.
- ARChon utilizes Google Chrome, and lets you install Android apps as if they were Chrome apps. It's pretty neat, though here too, compatibility is not perfect.
- Finally, Google are officially bringing the Play Store to Chrome OS. Since this is an official project developed by Google, I believe it should have the best compatibility of the lot. Chrome OS is a Linux distro, based on Gentoo. The bulk of its source code is made available through the Chromium OS project. This source code being available, it shouldn't be too hard to port this compatibility to popular GNU/Linux distributions. Google are relatively friendly to open source (at least compared to Apple/Microsoft), and I don't think they'll be throwing up any roadblocks to such porting. If anything, they seem keen on the Play Store hitting as many devices as possible. They may even build this functionality into future versions of Google Chrome for Linux, or release a separate package. They release most of the source code for both Android and Chrome OS, and they use Linux internally.
By the way, there is no need to compile APKs separately for x86. The apps you write are compiled into Dalvik Executable (DEX) code, which is finally converted into assembly code (according to the required architecture) by the kernel to send to the processor. (This last part is taken from this answer.)