You can chroot into more or less any ARM Linux distribution from within Android, and you only need to use VNC if you want to run X applications (since Android doesn't use an X server), which strictly speaking isn't necessary for most of the tools you would be using.
So it is really just a matter of finding (or compiling) ARM builds of whatever applications or tools you want to run, and installing them under your chroot'd install.
Alternately, it is also possible to build native Linux applications for Android (this is different than using the NDK), but that raises it's own problems as Linux code must be built against Bionic (Android's custom version of libc), which is not 100% compatible with the standard GNU libraries. You could build everything static, but at that point you are looking at more work than it is probably worth unless there are only one or two tools you really want. For example, I have tcpdump installed on my phone that way.