mysql-server-coreおよびmysql-client-coreのバージョンは自分の環境に合わせて適宜変更してください。
sudo apt-get purge mysql-server mysql-client mysql-common mysql-server-core-5.X mysql-client-core-5.X
sudo rm -rf /etc/mysql /var/lib/mysql
sudo apt-get autoremove
sudo apt-get autoclean