Desde 17 de fevereiro, existe um fork do rxvt-unicode que faz exatamente o que eu estava procurando. Através dos recursos X, você pode personalizar todas as 256 cores. Cada cor pode ser configurada para qualquer um dos trigêmeos 2 ^ 24 RGB.
Em um Ubuntu 11.04 recém-instalado, a instalação é feita assim:
sudo apt-get install libperl-dev libx11-dev libxft-dev git g++
git clone https://github.com/trapd00r/rxvt-unicode.git
cd rxvt-unicode
sh configure --enable-256-color --enable-font-styles \
--enable-perl--enable-mousewheel --enable-lastlog --enable-xft
make
make install