Fatal error: Can't open and lock privilege tables: Table 'mysql.host' doesn't exist

After chown and chgrp'ing /var/lib/mysql per the answer by @Bad Programmer, you may also have to execute the following command:

sudo mysql_install_db --user=mysql --ldata=/var/lib/mysql

Then restart your mysqld.

1. Uninstall mysql using yum remove mysql*

2. Recursively delete /usr/bin/mysql and /var/lib/mysql

3. Delete the file /etc/my.cnf.rmp

4. Use ps -e to check the processes to make sure mysql isn't still running.

5. Reboot server with reboot

6. Run yum install mysql-server. This also seems to install the mysql client as a dependency.

7. Give mysql ownership and group priveleges with:

   chown -R mysql /var/lib/mysql

   chgrp -R mysql /var/lib/mysql

8. Use service mysqld start to start MySQL Daemon.

I had this issue on arch linux as well. The issue was pacman installed the package in a different location than MySQL was expecting. I was able to fix the issue with this:

sudo mysql_install_db --user=mysql --basedir=/usr/ --ldata=/var/lib/mysql/

Hope this helps someone!