Se você quer o caminho oficial, você deve atualizar para o 12.10 ou superior.
Mas o caminho indireto é Servidor Percona com XtraDB fornecendo libmysqlclient-dev 5.6 versão. Então, se você adicionar seu PPA, ele lhe dará uma maneira de instalar o libmysqlclient-dev 5.6.
Para adicioná-lo, faça isso no seu terminal
gpg --keyserver hkp://keys.gnupg.net --recv-keys 1C4CBDCDCD2EFD2A
gpg -a --export CD2EFD2A | apt-key add -
sudo sh -c 'echo "deb http://repo.percona.com/apt precise main" >> /etc/apt/sources.list.d/percona.list'
Então sudo apt-get update
tente novamente.