Se você está vinculado apenas ao MySQL, não há uma solução fácil.

Normalmente, isso é resolvido usando indexação de ngram especializada para filtragem rápida de pesquisa de candidatos e, em seguida, calculando o levensthein apenas em 10 a 50 candidatos, o que é mais rápido que o cálculo do levensthein para todos os pares.

Mecanismos de pesquisa de texto completo especializados, como Solr/Lucene, têm isso integrado.

O PostgreSQL tem o módulo contrib pg_trgm (http://www.postgresql.org/docs/9.0/static/pgtrgm.html) que funciona muito bem.

Você pode até simular isso no MySQL usando indexação de texto completo, mas você precisa coletar palavras de todos os seus documentos, convertê-las em ngrams, criar índices de texto completo neles e cortá-los todos juntos para uma pesquisa rápida. O que traz todos os tipos de problemas com redundância, sincronização... não vale o seu tempo.