Okay. So instead of the old-time Bluetooth DUN i looked a bit into Bluetooth PAN. And it turns out it's actually a lot easier than Bluetooth DUN.

From a root terminal:
0. apt-get install bluez-gnome, edit /etc/xdg/autostart/bluetooth-applet.desktop to show in LXDE as well (if you use nit-env-lxde)
1. reboot.

2. Find the BDADDR of your phone with a hcitool scan
3. Set up the BNET link with pand –connect <BDADDR> –service NAP
3a. It will probably ask you for PIN/Pairing around this point.
4. Set up TCP/IP networking with the DHCP client of your choice, such as dhclient bnep0

Can some of you Deblet users try it out and tell me if it works for their phones or not, and what models/providers?

You can kill the connection with pand --kill <BDADDR> again.