Caps probably aren't bad, 16V rating used at 5V should still be over 50%, hopefully more like 80% of rated. Question remains, why 3.9uH inductor when the datasheet says 2.2?
I'm not so offended by the layout. Things could be closer, but that obviously doesn't matter on the inductor side, only the input side. You can try tacking a small (1 or 0.1uF) cap across the VCC/GND pins, directly on the pins, to see if it affects anything; I'm guessing not.
A solid ground plane would be nice (e.g., via stitched to the bottom layer, rather than single sided), but as long as it's connected underneath the chip, it can't be terrifically bad.
I don't know why it takes time to go nuts, but the problem is definitely compensation. Ripple is clearly visible during the oscillation, it's not shutting down or anything. A prime suspect is using component values too large or too small for the internal compensation. The 3.9uH inductor seems the most likely culprit.
And again, the datasheet says very little about ESR, so a tantalum (not electrolytic -- ESR too high) would be good to try, or a small chip resistor (0.1-2 ohm) in series with the output filter cap, to see if that helps. Again, L, C and ESR all factor into the loop stability, and if they aren't exactly what the chip is designed for, you get this.
Tim