Likely not hard with 95, but easier with 98 and 98SE, as the boot floppy has CDROM support for most drives. If you can use a 98 or 98SE install CD and it's boot floppy, you'll be able to get it re-setup.
I had a friend in that same situation, but looping in between 98 and win 2000, had him boot to a 98SE floppy and format the drive, then run my CD I sent him, which was a full 98SE install.