Levenshtein vs MATCH vs Others for best MySQL string match
A FULLTEXT index is very efficient for small resultsets in a huge table.  Using levenshtein involves checking each row.  So, I agree with your approach to do FT as a first step.

I would suggest


Remove short words, etc, from the string.  (not necessary for MyISAM since it ignores them; necessary for InnoDB, else it returns nothing)
IN BOOLEAN MODE but without any "+" on the words;
ORDER BY MATCH... DESC and add LIMIT.  This keeps edge cases from coming up with thousands of rows for the next step.
Check levenshtein distance.


Keep in mind that the end result will be less than perfect, but at least it should be "fast enough".