Tente instalar o pacote gcc-4.5-base:
$ sudo apt-get install gcc-4.5-base
Você pode precisar instalar uma versão específica desse pacote. Verifique o log de alterações do pacote .
Para instalar a última atualização 4.5.1, tente:
$ sudo apt-get install gcc-4.5-base=4.5.1-12
(note que 4.5.1-12 foi marcado como experimental no log de alterações. Este é apenas um exemplo!)
Para mais informações sobre como instalar versões antigas de pacotes com o apt, dê uma olhada em: