We just got through reviewing MicroPython on the ESP8266, and one of the main takehomes is that our ESP modules need more flash memory. You may be in the same boat — the earliest (and cheapest) modules on the market only had 512 kB of flash. For over-the-air programming, or to give you some more space for fancier programs, you’re going to want 1 MB or even 4 MB.
The solution? Just buy a new flash chip and solder it on. This is especially easy if you’ve got an ESP-01, ESP-03, or ESP-11 modules where the flash chip is exposed. Desolder, resolder, done. It can be a little trickier for those modules with a tin can around chips, but that’s nothing that a little hot air can’t fix. See the video embedded below for a good walk-through.