I now have a PPP daemon running on my Cube, accepting incoming connections via Bluetooth. Works like a charm for mail and web surfing with my Newton, using Blunt. It's almost like WiFi, only the power consumption is lower. The setup is quite simple: Add a new serial port on the Mac via the Bluetooth Serial Utility, add a Bluetooth internet setup with the correct name server and other parameters, enable IP forwarding with ipfw and natd and start pppd on the new serial port.
These are the commands I used to enable IP forwarding (en1 is my outgoing interface):
I'm behind a firewall, so there are no other fancy filtering rules. The firewall is at 10.0.1.1, so that should be the default route to the outside world. The pppd command line looks like this (Bluetooth-Serial is the name I gave to my serial port):
When discovering services from the Newton, there are now two serial ports, and one of them is the new serial port. The other is the PDA sync port. Unfortunately, the exact port numbers seem to change, but it's easy to find out using trial and error.