Podéis instalar la versión más reciente estable de PHP 5.4 en vuestro Ubuntu muy fácilmente gracias a este repositorio:
https://launchpad.net/~ondrej/+archive/php5 [1]
Añadid el repositorio siguiendo estos pasos y debería funcionar (provado en Ubuntu 12.04):
sudo add-apt-repository ppa:ondrej/php5
Nota (a 23/11/2013): Parece ser que este repositorio es en el que el usuario (ondrej) pretende tener los paquetes más actualizados (php 5.5 y apache 2.4 ahora mismo). Si lo que queréis es utilizar la última versión de php 5.4 (old stable) tenéis que utilizar este otro repositorio en su lugar:
ppa:ondrej/php5-oldstable
Si no tenéis el comando add-apt-repository es porque no tenéis el paquete python-software-properties instalado. Instaladlo con aptitude si es así y podréis ejecutar el comando sin problemas.
Una vez añadido el repositorio actualizáis la lista de paquetes:
sudo apt-get update
E instaláis php5:
sudo apt-get install php5 php5-cli php5-whatever
Probado en Ubuntu 11.10 y 12.04 x64 tanto con el módulo de apache mod_php5 como con fastFCGI (con apache en modo worker).