How do these new-fangled phone chargers achieve step-down?
These are called switched-mode or switching power supplies.

Yes, they still have a transformer inside. That's necessary, otherwise the low-voltage side wouldn't be touch-safe.
The transformer is kept very small. That's possible because it works at a very high frequency; the mains voltage is rectified and a high-frequency switcher feeds the transformer. The higher the frequency the better the energy transfer between primary and secondary are. Remember that transformers only work on variations in current/magnetic field, so a higher frequency makes for more changes.  

Power supplies like this are not only recognizable by their light weight, they usually accept a wide range of input voltages as well, like 100V to 240V.

edit
This is a clever method which allows using a small transformer:  



Here the high frequency comes from two spikes per 50/60Hz period, where a capacitor discharges into the transformer when a small thyristor switches the voltage near its maximum. Due to the brief transfers (once per 10/8.33ms) this is only suitable for low power applications. The schematic shows a 150mW supply.