Here is another link you might find interesting.
http://whiteboard.ping.se/Android/Debian
I am not claiming to be an expert in any of these areas and am just a hobbyist so please do your own research before just taking my word for it but here are some things I have found. If anyone has any more or more accurate information, please do chime in.
As I've been looking into this more again I'm remembering some things I had read the first time around concerning this. For one, it is worthwhile to note that android is running a modified version of linux which is tailored to your device and is responsible for making sure all the hardware in your device works as expected. It is also worthwhile to note that linux is
not an operating system, it is a kernel. I'm assuming what you're really wanting on android is gnu.
From what I remember, this might be more easily accomplished by keeping the android kernel but replacing everything else. This would be done by changing the initramfs. You can found out more about this by looking at
this thread.