"There's really not a lot of options out there. You might consider using NX technology instead of VNC -- see FreeNX, NeatX, and OpenNX for open source versions, or NoMachine for a commercial version.
Here's the status of all VNC servers I know about:
RealVNC Free version. Fix your compile issues, and reconstruct the patch from this 2006 report that allowed Xvnc + XRENDER to work. The patch link seems to be dead, but reconstructing the patch from his sources may be possible. RealVNC Enterprise Edition supports XRENDER in v4.5. Unfortunately, the only supported Ubuntu versions are the LTS versions and 7.10-8.10. If you are willing to buy a license key, I'd contact support and see if they have a beta build for Ubuntu 9.04. xf4vnc claims XRENDER support. There's no package for it, and it's been around a while, but it seems to still have some activity. It seems to require modifications to XFree86 drivers, which is why there's no Debian/Ubuntu package. But you may be able to compile and install locally.
These provide a VNC server module to an existing Xserver. As such, if you can configure an underlying Xserver with Xrender support, you might be able to use one of these.
Vino, GNOME's builtin VNC server, seems to. krfbb, KDE's version. x11vnc, a VNC server not tied to any desktop environment.
The following VNC Xservers do not provide XRENDER support insofar as I can tell: