Eu geralmente faço batota e despejo do banco de dados em texto, e depois uso sed (ou Notepad ++ se o banco de dados for pequeno o suficiente). Exceto isso, é mais fácil fazer isso de forma programática usando Perl ou Python.
Fazer esse tipo de manipulação com SQL direto é doloroso. Se você fizer isso, eu recomendo strongmente que você evite SUBSTITUIR. Isto não é o que normalmente é usado. Se você for fazer uma alteração em massa nas linhas existentes, use o UPDATE por si só.