Удаляем все установленные версии и связанные пакеты mysql

dpkg -l | grep mysql

sudo apt-get remove <packets>

На месте packets пишем список пакетов из предыдущей команды. Пакеты вида lib* удалять не обязательно, но возможно они удаляться как зависимые.

Добавляем репозиторий с доступным пакетом в список наших репозиториев

echo "deb http://archive.ubuntu.com/ubuntu trusty universe" >  /etc/apt/sources.list.d/archive.ubuntu.com-trusty.list

Устанавливаем:

sudo apt-get install mysql-server-5.6