¿Es posible ejecutar aplicaciones de Android en Linux (normal)?

Aún no existe algo así, ya que las aplicaciones no se ejecutan nativamente en el sistema operativo, sino que en su lugar utilizan la Máquina Virtual Dalvik (Wikipedia). Es algo comparable a Java en el sentido de que utiliza bytecode y crea un entorno separado para cada aplicación. Por lo tanto, a menos que el entorno Dalvik sea portado a otras plataformas, no podrán ser ejecutadas en hardware normal.

Existe un proyecto llamado Alien Dalvik de Myriad que intenta ejecutar aplicaciones de Android en diferentes entornos, pero no hay mucha información al respecto. Myriad Alien Dalvik

Las cosas han cambiado un poco en los años desde que esto fue publicado.

Ahora hay varias formas (aunque ninguna de ellas perfectas todavía) de ejecutar aplicaciones de Android en Linux sin un emulador o máquina virtual.

1. Shashlik cuenta con una integración bastante buena con tu entorno de escritorio de GNU. Sin embargo, carece de Servicios de Google Play.
2. ARChon utiliza Google Chrome y te permite instalar aplicaciones de Android como si fueran aplicaciones de Chrome. Es bastante interesante, aunque aquí también, la compatibilidad no es perfecta.
3. Finalmente, Google está introduciendo oficialmente la Play Store en Chrome OS. Dado que este es un proyecto oficial desarrollado por Google, creo que debería tener la mejor compatibilidad de todas. Chrome OS es una distribución de Linux, basada en Gentoo. La mayor parte de su código fuente está disponible a través del proyecto Chromium OS. Al estar disponible este código fuente, no debería ser muy difícil portar esta compatibilidad a distribuciones populares de GNU/Linux. Google es relativamente amigable con el código abierto (al menos en comparación con Apple/Microsoft), y no creo que pongan obstáculos a dicho porteo. De hecho, parecen estar interesados en que la Play Store llegue a la mayor cantidad de dispositivos posible. Incluso podrían incorporar esta funcionalidad en futuras versiones de Google Chrome para Linux, o lanzar un paquete aparte. Publican la mayor parte del código fuente tanto de Android como de Chrome OS, y utilizan Linux internamente.

Por cierto, no es necesario compilar APKs por separado para x86. Las aplicaciones que escribes se compilan en código Dalvik Ejecutable (DEX), que finalmente se convierte en código ensamblador (según la arquitectura requerida) por el núcleo para enviar al procesador. (Esta última parte se toma de esta respuesta.)