How does a wireless charger work without a magnetic core passing through both "coils"?

the alternating current in the primary coil induces alternating electromagnetic field in the core and that field induces current in the secondary coil

Yes, but "in the core" is not necessary. A coil creates a magnetic field all around it, whether there's a core there or not. The core just confines the magnetic field so that less of it "leaks", which makes the transformer more efficient.

You can also make the transmission more efficient by putting a capacitor in series with both coils so that they resonate at the same frequency: http://en.wikipedia.org/wiki/Resonant_inductive_coupling

A good example of electromagnetic induction without a metal core is a passive RFID tag, which has no battery. Instead, its draws power from the reader, which sends out electromagnetic waves that induce a current in the tag's antenna. The distance between the tag and the reader can be several inches. Obviously at this distance, very little power can be transmitted, but it illustrates the principle.

A metal core is advisable because it concentrates the magnetic field. This makes magnetic coupling between coils more effective, but you can do it without the core too, especially if both coils are tightly coupled (mechanically close to each other). If you don't have a core and the two coils are some distance apart, part of the generated field will pass outside of the other coil.
(In a transformer the outside metal "shortcuts" the field, increasing it. Without this outside metal the field would fill a large volume around the core.)