most microcontrollers will work just fine with as low as 4.5v
also in reality rarely the usb voltage will be THAT low. Usually you'll only see as low as 4.7-4.8v due to voltage drop on the wires.
I would just use a very low vdrop linear regulator set to 5v, to simply smooth voltages above 5v. There are Microchip ldos that have 50mV drop or something like that so even if you get 4.8v at the input, the 5v ldo will output about 4.75v which should still be good enough for your microcontroller.
if you really want 5v, use a buck/boost regulator that can work in sepic mode. Higher frequency regulators will require smaller inductors and will work just fine with ceramic capacitors.. see LT1307 or LT1308 for example
(but they're a bit expensive being linear parts)