Il mysql_config eseguibile si trova per impostazione predefinita nella directory bin dell'installazione del server MySQL se lo installi da binari precompilati. Ma se lo installi usando apt-get potrebbe non esistere sul tuo server.
Prova:
sudo apt-get install libmysqlclient-dev
