Hmmm, partition tools won't touch the recovery partition? That sounds quirky! - it definitely should be possible. If nothing else, I would expect that diskpart is able to remove it - it usually isn't too fuzzy? If that fails, I'd be really
surprised if cfdisk (or similar) on Linux wouldn't be able to nuke it.
You say you have an image of the Windows partition... can't you make an image of the boot partition as well? I'd definitely try to leave it in place, as it's nice to have... and since you don't have any bootable Windows media, I dunno how you'd get the Windows partition bootable.
I guess you could grab the Win8 Enterprise ISO from Microsoft, and use that to create a bootable USB stick - you might
be able to use that to perform a boot repair. But you obviously shouldn't do an install with it, since you don't have an enterprise license (not talking morals here, simple matter of fact "for what I know, it won't work with a non-enterprise license key"