Well, the Native Development Kit (NDK) lets you build native code. There is a regular C/Unix environment underneath. If you look at a project like the Android Scripting Environment, they've managed to make Python, Ruby and Lua work on the phone, packaged as an .apk and not requiring root access. http://code.google.com/p/android-scripting/

You can compile pretty much anything for the phone, without needing root/Debian, though its not always as simple as 'apt-get install', for sure.

One way is to use the Native Development Kit, which lets you run regular C code on the phone. Here's a post explaining how to bind to bluez: http://blog.blackwhale.at/2009/08/android-bluetooth-on-steroids-with-the-ndk-and-bluez/

The other way is to use the existing android bluetooth API: http://code.google.com/p/android-bluetooth/

What that developer has done is use java reflection to wrap the existing (just not documented) android.bluetooth class API. I've been using it to communicate with an OBD-II adapter with some success (thought the dynamic port discovery API doesn't work entirely.)

For tethering, Wifi Tether works pretty well, since it doesn't even require the laptop to support bluetooth. It makes your phone a portable ad-hoc access point. Does require root access, for which there are some one-click solutions out there.