If you are interested, here is the detailed process (need to be adapted).

Check of package requiring a priority update

# rpm -qa centos\* redhat\*
redhat-menus-6.7.8-3.el5
centos-release-notes-5.4-4
redhat-logos-4.9.99-11.el5.centos
redhat-lsb-3.1-12.3.EL.el5.centos
centos-release-5-4.el5.centos.1

Retrieve from the installation media Redhat specific packages, or CentOS altered ones

redhat-logos-4.9.16-1.noarch.rpm
redhat-lsb-3.1-12.3.EL.i386.rpm
redhat-menus-6.7.8-3.el5.noarch.rpm
redhat-release-5Server-5.5.0.2.i386.rpm
redhat-release-notes-5Server-31.i386.rpm

We also need the RHN (Red Hat Network) access components to allow online update (and some dependencies)

pyOpenSSL-0.6-1.p24.7.2.2.i386.rpm
python-dmidecode-3.10.8-4.el5.i386.rpm
redhat-rpm-config-8.0.45-32.el5.noarch.rpm
rhel-instnum-1.0.9-1.el5.noarch.rpm
rhn-check-0.4.20-33.el5.noarch.rpm
rhn-client-tools-0.4.20-33.el5.noarch.rpm
rhnlib-2.5.22-3.el5.noarch.rpm
rhnsd-4.7.0-5.el5.i386.rpm
rhn-setup-0.4.20-33.el5.noarch.rpm
yum-rhn-plugin-0.5.4-15.el5.noarch.rpm

Remove the CentOS packages

# rpm -e --nodeps centos-release-notes-5.4-4 centos-release-5-4.el5.centos.1

Replace by the Redhat ones

# rpm -ivh redhat-release-5Server-5.5.0.2.i386.rpm \
           redhat-release-notes-5Server-31.i386.rpm

Update the altered packages

# rpm -Uvh --force \
    redhat-lsb-3.1-12.3.EL.i386.rpm \
    redhat-logos-4.9.16-1.noarch.rpm \
    redhat-menus-6.7.8-3.el5.noarch.rpm

Installation of RHN access

# rpm -ivh rhel-instnum-1.0.9-1.el5.noarch.rpm \
    rhn-check-0.4.20-33.el5.noarch.rpm \
    rhn-client-tools-0.4.20-33.el5.noarch.rpm \
    rhnlib-2.5.22-3.el5.noarch.rpm \
    rhnsd-4.7.0-5.el5.i386.rpm \
    rhn-setup-0.4.20-33.el5.noarch.rpm \
    yum-rhn-plugin-0.5.4-15.el5.noarch.rpm \
    python-dmidecode-3.10.8-4.el5.i386.rpm \
    pyOpenSSL-0.6-1.p24.7.2.2.i386.rpm

Register the system

# rhn_register

Before the update, i have to remove memcached because of a dependency issue with libevent (I have to look at this, hopefully, I don't use it)

# rpm -e memcached

Online update of new available versions 

# yum update
Install      3 Package(s)         
Update     125 Package(s)    

Reinstall other packages

# rpm -qa --qf "%{NAME} %{VENDOR}\n" | grep CentOS | cut -d' ' -f1 >lst
# yum reinstall $(cat lst)
Reinstall   347 Package(s)

Downgrade remaining package (list should be short)

# yum install yum-utils
# rpm -qa --qf "%{NAME} %{VENDOR}\n" | grep CentOS | grep -v kernel
# yumdownloader anacron specspo bluez-utils yum-metadata-parser \
    libmcrypt pango basesystem procmail setuptool yum-fastestmirror \
    pm-utils initscripts mhash
# rpm -Uvh --oldpackage anacron-2.3-45.el5.i386.rpm \
    specspo-13-1.el5.noarch.rpm \
    bluez-utils-3.7-2.2.i386.rpm \
    yum-metadata-parser-1.1.2-3.el5.i386.rpm \
    libmcrypt-2.5.7-5.el5.i386.rpm \
    pango-1.14.9-8.el5.i386.rpm \
    basesystem-8.0-5.1.1.noarch.rpm \
    procmail-3.22-17.1.i386.rpm \
    setuptool-1.19.2-1.i386.rpm \
    yum-fastestmirror-1.1.16-13.el5.noarch.rpm \
    pm-utils-0.99.3-10.el5.i386.rpm \
    initscripts-8.45.30-2.el5.i386.rpm \
    mhash-0.9.2-6.el5.remi.i386.rpm

It's done, a final reboot to switch to the new kernel and take all benefit from all updates.

# init 6
...
# cat /etc/redhat-release 
Red Hat Enterprise Linux Server release 5.5 (Tikanga)

Total elapsed time : less than one hour (with only 2' of services unavailability)

Who next ?