Strange oscillation in buck converter (AP3431)
It appears that the problem was with the shape of the traces on my PCB. The following PCB design works correctly: 



Unfortunately I still do not understand the real reasons behind this well enough to explain it, but I think it has to do with parasitic capacitance and inductance of the traces at high frequencies. It appears that at 1MHz these things really do matter, which also explains why I had so much trouble with the breadboard earlier.