gdisk is awesome.
But this fusion business is messy. I find the Disk Utility UI completely non-obvious. I don't really know that everything is being removed, as you say. Also, I'm not finding any guides that use Disk Utility to create a new fusion drive from scratch. All of them are using the command line 'diskutil corestorage' commands.
So I personally would have the 10.9 installer package on a USB stick and test to make sure you can boot that. And I'd also have another USB stick with a linux live CD like Fedora 19 on it, in case OS X doesn't like having it's live partitions deleted by gdisk while it's still running. You need to remove the partitions off both the SSD and HDD if you haven't found a sure fire way to do this in the Disk Utility UI (I haven't; I've found Disk Utility only shows the fusion drive, it doesn't show the actual physical SSD or HDD partitions that make up the fusion drive).
Then I'd try using gdisk to obliterate the partition maps on both physical drives. Start with diskutil list to make sure you have the actual physical drives nodes identified. They should be disk0 and disk1 for the SSD and HDD respectively. So the command to run gdisk is:
X is the number for the drive, found with diskutil list. Once in gdisk, you can use ? <return> to get a menu listing. Go to the experts menu, and again ? <return> to list expert menu options. Find the one to delete the GPT, I think it's z for zap. That will blow away both primary and backup GPTs, and optionally will erase the MBR also which is used for Windows. I would erase everything.
And do that for both the SSD and HDD.
Now you have no choice but to boot off the 10.9 USB stick. I think no matter what you'll use Disk Utility to create 1 partition on both SSD and HDD. If you can figure out how to make a fusion drive in the 10.9 Disk Utility, great. Otherwise you'll need one of the guides handy to do this with 'diskutil corestorage' Terminal commands. The Terminal is available from the minimal OS X system when booting from the USB stick (same environment as Recovery HD) but it's hidden in one of the drop down menus, it's not in the main visible menu.
My best guess is that you'll put the single large partition from the SSD and HDD into a corestorage logical volume group, and from that you'll create one big logical volume. That's the fusion drive. And the command will also include formatting and naming that LV whatever you want. JHFS+ is the usual option, or HFSX if you want case sensitive (I don't recommend it because some apps, especially Adobe apps, have all sorts of problems running on a case sensitive fs).
When you go to installer, the fusion drive shows up as the only target and install commences. Something I don't know about fusion drives, that normally happens with conventionally formatted disks, is the installer resizes the OS X volume to make room for Recovery HD. I'm virually certain this happens automatically as well for fusion drive installs, what I don't know is if both the SSD and HDD each get a Recovery HD, or only one of them. And if only one of them, I don't know which one. But presumably this gets figured out automatically for fusion drives as well as conventionally partitioned single disk installs.
I think it would be really useful if you can post the output from these commands before you get started. After 10.9 is installed. And after you use Bootcamp Assistant to create space for Windows. They don't need to be installed, as they're already included with OS X, and are read only commands that don't change anything on disk. If you can do this for both SSD and HDD it would be quite informative. Do this on disk0 and 1, from diskutil list. They won't return any useful information if you run it on the fusion drive itself (which is probably disk2).
Code:
sudo fdisk /dev/rdiskX
sudo gpt -r -vv show /dev/rdiskX