Primero aclarar d que no sobreescribe el SO Android, solo se ejecuta por encima. No afecta a anda en el sistema.
Tambien hay tutoriales de como instalar Ubuntu, Open Suse etc.... todo esta en google.

Bien empecemos:

Tutorial


A) Instalar Debian


Bajar los archivos necesarios desde este link: MEGAUPLOAD - The leading online storage and file delivery service
Conectar el celular a la PC en modo de almacenamiento, o sacarle la SD y conectarla a la PC con un adaptador o lector de tarjetas.

Crear en la memoria SD una carpeta con nombre "debian", y descomprimir dentro los archivos que contiene el zip.

Volver a colocar la SD en el celular, o desconectarlo de la PC.

Por seguridad, reiniciar el celular, ya que en algunas ocasiones el sistema de archivos queda como de solo lectura.

Desde un emulador de consola/terminal en el celular, ejecutar:
su
cd /sdcard/debian
sh installer.sh




B) Iniciar Debian y configurar las cosas básicas


Con lo hecho antes Debian ya está instalado, pero necesitamos levantarlo y hacer algunas configuraciones iniciales.


Desde un emulador de consola/terminal en el celular, ejecutar:
su
cd /sdcard/debian
sh bootdeb


Esto va a iniciar Debian. Cuando haya terminado de iniciar (les deja el prompt para empezar a escribir), ejecutar:
sh /scripts/onetime.sh

Esto nos va a pedir configurar una contraseña para el usuario root. Háganlo, es necesario.

Agregamos algunos repositorios básicos. Editamos el archivo /etc/apt/sources.list agregándole al final:

deb Index of /debian lenny main contrib non-free
deb-src Index of /debian lenny main contrib non-free

Agregamos la configuración básica para que pueda utilizar la conexión de internet wifi del celular. Editamos el archivo /etc/network/interfaces y le agregamos al final:

auto tiwlan0
iface tiwlan0 inet dhcp



Después de hacer esto, tenemos que salir de Debian ejecutando:
exit

Ahora, cada vez que queramos levantar Debian, ejecutamos:

su
cd /sdcard/debian
sh bootdeb


Y siempre hay que salir usando "exit" (y no cerrando la aplicación así nomás)



Con esto ya es suficiente para tener un Debian desde línea de comandos. Los tutoriales que siguen son completamente opcionales.


C) Aumentar el tamaño del sistema de archivos


El Debian que tenemos instalado corre sobre un sistema de archivos contenido en un archivo de imagen, el debian.img. Esa imagen puede resultar un poco chica si vamos a instalar un entorno gráfico, o muchas aplicaciones. Así que si necesitamos hacerla más grande, estos son los pasos:


Prestar atención a dónde se debe ejecutar cada comando, si en el celular o en la PC!.

Conectar el celular a la PC en modo de almacenamiento, o sacarle la SD y conectarla a la PC con un adaptador o lector de tarjetas.

Copiar el archivo debian.img de la SD a una carpeta en la PC, que a partir de ahora llamaremos PATH_PC

Desde la consola/terminal de la pc, ejecutar esto reemplazando TAMAÑO por el tamaño que queramos. Ejemplo: para 3.5 GB poner 3500999999:
cd PATH_PC
dd if=/dev/zero of=debian2.img seek=TAMAÑO bs=1 count=1
mke2fs -F debian2.img
mkdir debian
mkdir debian2
mount -o loop debian.img debian
mount -o loop debian2.img debian2
cd PATH_PC/debian
cp -R -f * PATH_PC/debian2
umount debian
umount debian2

(si no funciona reinicar la pc y volver a intentar)
cd PATH_PC
rm -r -f debian
rm -r -f debian2
rm debian.img
mv debian2.img debian.img
chmod a+x debian.img
chmod 777 debian.img


Copiar el archivo debian.img de la PC a la carpeta debian de la SD.

Volver a colocar la SD en el celular, o desconectarlo de la PC.

Por seguridad, reiniciar el celular, ya que en algunas ocasiones el sistema de archivos queda como de solo lectura.

Desde un emulador de consola/terminal en el celular, ejecutar:
su
cd /sdcard/debian
sh bootdeb

(eso nos inicia Debian, ya deberían saberlo, jeje)
cd /var/lib/dpkg/updates
rm -r -f *
dpkg --configure -a




Después de hacer esto, tenemos ya un Debian con mucho más tamaño para jugar


D) Instalar un entorno gráfico


Para asombrar a nuestros linuxeros amigos, podemos instalar un entorno gráfico completo y jugar con nuestro Android como si fuese una PC de escritorio. Se arrastra de lento, y a veces se cierra solo por falta de memoria, pero anda al menos por los segundos necesarios para causar el efecto "waaaaah!"

Recordemos que si queremos instalar un entorno gráfico, deberíamos aumentar el tamaño del sistema de archivos.


Como los pasos no cambiaron del tutorial original, les dejo directamente el link a ese tutorial (si en algún momento desaparece, tengo una copia local, pidanme y la subo):