You dont need a Redhat Bootdisk, but if you would like one, you might be able to find the correct imgs for creating one, on Planetmirror.
You can use any LiveCD OS, such as SLAX, RescueCD. To recover your system. Boot the LiveCD, then once running,
cd /
mkdir TEST

Now mount the root Redhat (partition) system under Test, create any additional directories or mount the other necessary partitions underneath, example:
mount /dev/hda1 /TEST

Then change the current ROOT directory to the newly mounted dir.
chroot TEST

Since your now running on the RedHat system you should be able to navigate to where you need to go to reinstall the bootloader, run whatever it is to force a rewrite of the boot record.