re Debian: your best bet is one of the chroot on Android apps. With some more skills you can get closer to just Debian on a phone that shipped with Android. Unfortunately with the way mobile devices are created, you'll probably never get a new device from mass-market mobile device vendors that will run mainline Linux and so Debian will never support mass-market mobile devices. OTOH, you can run mainline Linux on ancient devices like the N900 or on expensive not yet built devices from non-traditional phone makers like the N900 or Pyra.
https://wiki.debian.org/ChrootOnAndroid https://wiki.debian.org/Mobile#Articles http://elinux.org/N900 http://neo900.org/ https://pyra-handheld.com/