Your HD Setup/ patched HD Setup will be on your Disk Tools floppy for whatever system you want to install, let's say 7.5 (a good choice, in my estimation, so long as it's on a 68k machine). You are going to need a new set of system floppies (available online), so the patched version of HD Setup would be located there. You'd boot from the Disk Tools floppy with the patched program, format your 3rd party drive, and away you'd go.
If you search these fora, you most likely will find locations from which to download 7.1 or 7.5; there is a version of 7.5 available on Apple's own servers. I'd stick with the plain-Jane 7.5, but some want to go higher.