You might want to consider
CentOS. That way you can get RHEL 4, without support. Or, if you have support from Red Hat through Red Hat Network, then consider upgrading to Red Hat Enterprise Linux 4, since it should be available to you through Red Hat Network. It would probably work better than downgrading to RHEL3.
Edit : In case you don't know, CentOS is RHEL minus Red Hat's trademarks.