I downloaded the following from a CentOS mirror into an empty directory (in my case, they're on my USB memory stick):

centos-release-4-2.1.i386.rpm
centos-yumconf-4-4.3.noarch.rpm
python-elementtree-1.2.6-4.i386.rpm
python-sqlite-1.1.6-1.i386.rpm
python-urlgrabber-2.9.6-2.noarch.rpm
RPM-GPG-KEY-centos4
sqlite-3.2.2-1.i386.rpm
yum-2.4.0-1.centos4.noarch.rpm

Then ran:

rpm --import RPM-GPG-KEY-centos4
rpm -e --nodeps redhat-release
rpm -Uvh *.rpm

then

yum upgrade

I've done this without problems on three boxes so far.

Cheers,

Phil