Not a Linux virtual machine, but an Android terminal emulator and Linux environment that works directly with no rooting or setup required. A minimal base system is installed automatically - additional packages are available using the APT package manager.
In both the Google Play and F-Droid stores.