Have a look at the following:
This is from the RH administration guide for RH4. Surprisingly the guide is still available.
Click on the next to go to the next page. Section A.2 (the second page) talks about what can cause your system to not recognize an existing installation during an upgrade and what you can do about it. I suspect that you will be in for a wild ride in any case, so make a good backup or an image before you begin.
The process pretty much comes down to making note of which packages were installed, saving the configuration files (predominantly in /etc) and performing an upgraded installation. Note that the instructions say that it saves your existing configuration files with the extension .rpmsave, which tells me that they aren't really doing an upgrade but a replacement and leaving it up to you to merge any changes back into the config files.
I will mention that something really seems "off" about what your trying to do and this "decisions beyond your control". The upgrade process for Red Hat was designed to go through the Red Hat Network. This is part of the service that you obtain when you buy Red Hat and get Red Hat support. According to the notification sent out at the beginning of the month, (March 1, 2012) if you are a Red Hat Subscriber you have access to all versions of Red Hat Linux as well as support). You should also take a look at this page:
which is the issues for RHEL 4 and show that to whomever the idiot making this very bad decision is and point out to them that this is the sort of thing that they will NOT be receiving. The bottom line is that if you want Red Hat without paying for Red Hat support and the Red hat Network go with CentOS instead of trying to obtain community support for a presumably illicit copy of Red Hat
If you do not have Red Hat Support, back up your configuration files, make a backup copy of your system onto a USB drive. Given the age of your system, a 500 Gb or 1Tb drive should be more than sufficient. Especially copy your /etc drive as well as any
you have in a place like /var. Here is a link (from a solid author) on obtaining a list of installed packages:
Obtain this list, and then re-install these packages after you upgrade your system. Then merge your configuration files as necessary.