No se requiere tener instalado ningún sistema operativo, lo que se hace en esos casos, es usar disquetes o CDs de arranque que los genera el mismo programa al momento de instalarlo, lo que si debes tener es definida la partición y formateada de acuerdo al sistema de archivos que definas (FAT O NTFS)., de esa manera te presenta el programa en versiós DOS, pero con un look muy similar al que tiene en windows.
Esta operación yo la hice hace +- un año, pero usando el Powerquest Drive Image 2002, grabé la imágen de la partición activa en CDs , luego instalé el disco nuevo, le hice las particiones e instalé todo el sistema en el nuevo disco en 20 minutos.
Yo te aconsejo que te consigas el Drive Image 2002, es ya un producto discotinuado por que la empresa que lo desarrolló fué adquirida por Symantec(Norton), pero en opinión de muchos, es el mejor clonador
Para recuperar tus datos, trata de conseguirte el "Hiren´s Boot CD", tiene muchas herramietas que te pueden ser útil.