Can a USB device attempt to be bus-powered and then fall-back to self-powered?
That defines a normal enumeration process. If it doesn't work for you that way, and you are programming the USB peripheral side, then you could do this without issue.

Enumerate, failed at 500 mA request. The Host should signal this enumeration failure according to the Specs.

Device disconnects the usb data pins, changes its usb descriptor, and signals for enumeration again.

If failed. Repeat, changing it's descriptor to read self powered again. 
You must have a method to switch the power pin. A usb power switch for example. A diode OR bridge if the voltage drop is acceptable. You cannot back feed the VUSB with your battery unless you want to break something. Then signal again. 

The descriptor is nothing but a few bytes that you could change via variables. As long as you can change that, you are fine.