For anyone having the same symptoms: The problem can also be due the power supply not being able to handle the ESP's current spikes.
Measure the voltage directly between the VCC and GND pins of the ESP.
In my setup (cheap breadboard 3.3V power supply, flimsy 100nF cap somewhere in circuit between V+ and GND), I measured only 2.2V.
To test, I added a 3300uF capacitor directly between those pins, and now the ESP runs and I'm measuring 3.0V. I really should get a better power supply, though -- the capacitor is twice the size than the ESP.
I should have known. In case of inexplicable problems, check power first. There's also a video on properly powering your ESP: https://www.youtube.com/watch?v=wf_msvWv1jk