Não há nenhum pacote PHP4 no Ubuntu 9.10.
Eu acho que você pode baixar a fonte PHP4 do link e compilá-la você mesmo.
Eu mesmo baixaria o Ubuntu 6.06 ainda suportado, que possui pacotes PHP4, e o instala em uma máquina virtual. Dessa forma eu poderia brincar com coisas antigas sem causar conflitos com o meu sistema atual. Você pode encontrar arquivos iso do Ubuntu 6.06 no link