EDIT: Both my posts have been approved now so I'm gonna merge them into one. I've managed to resolve the issue.
The ESP-01 has actually 512kB+512kB flash (firmware+storage). This means that the flash chip is actually 8m instead of 4m and we have to push the init data to the other address as well!
Here's what made my ESP-01 work (check the previously mentioned flashing guide for init data file download)
$ tools/esptool.py --port <your_port> write_flash --verify --flash_mode qio --flash_size 8m 0x00000 bin/<your_firmware> 0xfc000 esp_init_data_default.bin
For the dev board just change flash_size and flash_mode as per the flashing guide and flash init data to 4MB address