The easiest way I have found is to dump the database to a text file, run a sed command to do the replace, and reload the database back into MySQL.
All commands are bash on Linux, from memory.
Dump database to text file
mysqldump -u user -p databasename > ./db.sql
Run sed command to find/replace target string
sed -i 's/oldString/newString/g' ./db.sql
Reload the database into MySQL
mysql -u user -p databasename < ./db.sql
Easy peasy.