Ou alternativamente para os instantâneos do Debian, Elazar postou em sua resposta , você pode usar os repositórios de pacotes do Ubuntu para versões antigas do Ubuntu: link
Adicione-os ao /etc/apt/sources.list
como Elazar já descrito:
deb http://archive.ubuntu.com/ubuntu/ hardy universe
deb-src http://archive.ubuntu.com/ubuntu/ hardy universe
O repositório do Hardy Universe é o que contém o gcc-3.4.