Are there any Android phones that allow Bluetooth PAN off the shelf?
Android 4.0 devices (or already 3.0?) allow this.

Both client and host PAN roles are supported (I guess this was deliberately introduced by Google for UMTS-less tablets).

On the PAN host: Enable bluetooth tethering in the settings
On each device: Pair with the host and enable "Internet access" in the bluetooth device's tab: