You can't put even a minimal kernel+compressed ramdisk distro on a 512k BIOS Flash ROM, even with LinuxBIOS. I'd be happy to be proven wrong. I'd say 2 MB (about the size of a floppy) is about the minimum for useful userland stuff.
The best option is to use an IDE->compact flash daughter-card that fits into the IDE header on the motherboard, and use obsolete 8 to 32 MB CF cards that are widely available at obsolete consumer electronics prices, i.e. 0$.
I might even design the PCB and place the layout somewhere accessible, if these daughter cards are not available commercially.