Ok so I have solved the problem without re-formatting or re-installing. Hopefully most people won't wind up in this situation. See @robmathers answer for tips on how to avoid deleting your Recovery HD in the first place.
WARNING the following commands are fairly low-level and may cause you to loose data. Take proper precautions (backup, clone, etc).
But for anyone in my situation after the RecoveryHD is already gone, here is what I did:
- Backup all data / clone your drive
- Create a bootable USB (or use an existing HD) with 10.8
- Boot into that alternate drive (so you're not modifying the HD you've currently mounted)
- Unmount the Fusion HD
- Open terminal, switch to superuser and follow these instructions:
List the current configuration, and make a note of which drives you'll be modifying. Your exact sizes and GUIDs will be different than mine. It is crucial to use your numbers instead of mine.
diskutil corestorage list
Take note of the UUID of the physical drive you're adding the Recovery to.
Take note of the exact size in bytes of the Recovery on the current startup disk (disk2s3 might be different for you).
diskutil info disk2s3
Resize the Physical Volume for the drive you want to add the Recovery partition to. To determine the size, look @ the existing Recovery partition on the USB. In my case it was just under 1GB. For the following command, pvUUID is the UUID of the drive you're adding the Recovery to, size is 1GB less than the current size.
diskutil coreStorage resizeDisk <pvUUID> <size> JHFS+ Recovery 784220160B
NOTE: you may need to unmount the volumes repeatedly in the following steps. OSX tends to aggressively re-mount the volumes.
Repartition the new "Recovery" partition from a jHFS+ to Apple_Boot. First, take note of the exact start/size of the partition.
gpt show disk0
start size index contents
0 1 PMBR
1 1 Pri GPT header
2 32 Pri GPT table
40 409600 1 GPT part - C12A7328-F81F-11D2-BA4B-00A0C93EC93B
409640 246725744 2 GPT part - 48465300-0000-11AA-AA11-00306543ECAC
**247397528 1269528 3 GPT part - 48465300-0000-11AA-AA11-00306543ECAC**
250069647 32 Sec GPT table
250069679 1 Sec GPT header
Now remove the partition, and re-add it with a different UUID (the UUID is what determines the type of partition)
gpt remove -b 247397528 -s 1269528 -t 48465300-0000-11AA-AA11-00306543ECAC disk0
gpt add -b 247397528 -s 1269528 -t 426F6F74-0000-11AA-AA11-00306543ECAC disk0
Now copy the entire Recovery partition from the good one to this new one:
dd if=/dev/disk2s3 of=/dev/disk0s3
Many thanks to the following sites for reference. Read up on them before diving in, if you don't understand any of these steps.