Android is based on Linux; can native Linux applications be run on Android?
In general, no. Android apps generally run in a sandboxed Java-like virtual machine, so have to be written in Java or some language that compiles to virtual-machine bytecode that use the Android API.
However, the virtual machine does run on top of the underlying Linux OS, and there are ways to call native code. See https://developer.android.com/tools/sdk/ndk/index.html
So, while it is technically possible to run native Linux programs, as there is a Linux kernel running beneath everything, most users would not be able to install such applications or use them. (If you have root access or are building your own firmware, then you can do whatever you want.)
Yes you can. I have installed a complete Debian distribution in a chroot-jail enviroment using debootstrap. (You need a rooted device) I am now running ssh, apache, mysql, php and even a samba server under android on my htc-desire with no problems. It is possible to run x applications using a remote x server via ssh. It even runs openoffice.org and firefox. You can use this: http://code.google.com/p/android-xserver/ to run X-application on localhost but my HTC-desire has a to small screen to be productive :-) But it might be usefull on a Eee Pad Transformer or something like that.