How do the tiny AC->USB power supplies work?
This is not limited to these USB charger supplies.  Most modern "wall wart" type power supplies are like this.  They can be small because they are switchers.  The line power is full wave rectified, then the result chopped at high frequency thru a transformer.  The much higher frequency allows for a much smaller transformer to handle the same power.  5 Watts (5 V at 1 A) is easily doable in something that fits in the palm of your hand.

If you dig around, you can probably find a schematic for a small switcher like this.  It is usually a full wave bridge, cap, and some sort of oscillator driving the primary of a small transformer at a few 100 kHz.  The output of the transformer is rectified, filtered, and the result compared to the voltage setpoint.  The over/under voltage indication is then transmitted back to the oscillator on the high voltage side via a opto-coupler.