To have rsyslog working correctly on RHEL 4 or 5, some conditions have to be met. The method described has been tested with rsyslog 5.7.1.
First of all compile and install the dependencies.
After that, you can install rsyslog using the following commands:
./configure PKG_CONFIG_PATH=/usr/local/lib/pkgconfig --enable-gnutls make make install
It could happen, that the install might complain about gnutls.pc. Simply comment out the URL found near the start of the file /usr/local/lib/pkgconfig/gnutls.pc.
Credit for this find goes to Forum member Johann Reinhard (johannreinhard).