For all the newer versions of Windows you NEED a CD-ROM but Windows 95 and older are avalible on floppy disk. You might be able to find these disks on eBay or some other auction site. So you know I have lost my Windows disk but have the setup files on my Hard Disk. Before a format I create an extra partition big enough for the setup files, copy the files to this partition. Format the first partition (the one with Windows on) then run the setup files from the other partition. Once I'm back up and running I can get rid of the partition with the setup files.
Hope this helps and sorry it's a bit on the long side.