Use usort()
(http://us2.php.net/manual/en/function.usort.php), and have your compare function use the Levenshtein distance.
If that value is expensive to compute, then pre-compute it and store it in a separate array so that your compare function doesn't have to recompute it frequently during the sort.