Oh well, a bounty! I finally went with this non hideous looking circuit that still oscillates at battery voltage, but stable at above battery voltage! Battery voltage is likely to be max 4.5V with lead acid, which is the lower limit of the USB spec.
The trouble is not the mains voltage which may not be stable. It may be unstable for just an instant and is not an issue. If it is really unstable or out of spec, replace the wall wart. There may be many things wrong with a wall wart that cannot maintain voltage. Would not want to trust it to power microcontrollers.
The real problem is the battery voltage which needs to be cut off once it falls too low to avoid permanently damaging the battery. Adjust resistors to taste. Circuit is less expensive than before, and more reliable. Schottky is my friend, I don't mind him anymore! He saved me a lot of headache. The circuit running from battery needs to be able to operate at far lower than 4.7V anyway.
PS: I don't like single chip solutions, they play hard to get on my side of the planet. Besides, I can't smoke them willy nilly...
Here's a much more elegant (non hideous) looking schematic. As Dorian and others have pointed out, the TL431 requires a minimum current to operate. So then, it requires a reliable voltage source to operate. Which means, it has to operate from the battery. The TL431 really has to act as a comparator, otherwise the mosfets will be in linear mode and will start to heat up. The gate voltage becomes very close to source voltage of U2 due to mains voltage coming in. This is the actual cause of the oscillations above, not the datasheet violation of the tl431. The oscillations will happen even if the tl431 is removed completely. The mosfets being logic level does not help either. For the circuit below, the mosfets have been replaced with N channel mosfets. However, this causes a voltage drop at source when fully on. Voltage to load varies from 2.8V to 4.7V and the circuit works perfectly without oscillations. It may be possible to switch position of R6 and the tl431, but then the tl431 anode will only go up to 2.5V, and the mosfets (now replaced again with P channel mosfets) will always remain on.
But then, since the tl431 is being used as a comparator anyway, and also requires a supply current to work, why not replace it altogether with a lower current comparator like device.... Unfortunately, lm358 does not reach the +ve rail, and the mosfets are logic level. So when the mains voltage is high, a reverse current flows into the battery (0-60mA when battery drops from 3.85 to 3.6V). This will trickle charge the battery when charge goes low. That may hopefully be a good thing. Circuit works perfectly at all mains voltages from 2V to 5V, with no oscillation. Circuit does depend on the voltage drop across the diode. Replacing it with 1N4148 will not guarantee it's working without oscillations if battery voltage is high. Circuit did not simulate correctly with the LM393 which is an actual comparator. Proper testing is suggested before use.
Oscillations are caused by some kind of race conditions at the source and gate voltages of the second mosfet. I still don't know exactly what is going on. But the modified circuits work, and solves my problems. This is not the perfect answer. But it is the best answer. I am accepting my own answer.
Tweaked again, look closely, mosfets are flipped on the Y axis so source is inside. Circuit is now fully stable at all mains and battery voltages. Depending on the mains to battery voltage difference some trickle current may flow to the battery (maybe 60mA) in some cases. Circuit works with either a schottky or a 1n4148 (although obviously with 1n4148 it will draw from battery more if battery voltage is high). Works with real comparator LM393 as well as LM358, with no changes. Opamp/comparator accepts mains or output voltage at non inverting pin for comparison with battery. I think it's close to perfect. Thanks for the bounty!
PS: probably should replace 1N4148 with 1N4007, but 1N5819 is best.