The Levenshtein distance is really a bit more general than between two permutations; it is defined between two strings (of the same or varying lengths). There are more common notions of distance between permutations, e.g., the Kendall tau distance or others.
Searching for "distance between rankings" may be more fruitful than searching for "permutations". Similar for "probability distribution/density on rankings". And lo and behold, we find a paper by Critchlow et al. (1991, Journal of Mathematical Psychology) that sounds very promising:
This paper investigates many of the probability models on permutations that have been proposed in the statistical and psychological literature. The various models are categorized into the following general classes: (1) Thurstone order statistics models, (2) ranking models induced by paired comparisons, (3) ranking models based on distances between permutations, and (4) multistage ranking models. Several thematic properties of ranking models are introduced that provide the basis for a systematic study of each of the classes of models. These properties are label-invariance, reversibility, strong unimodality, complete consensus, and L-decomposability. Next, several important subclasses of the four general classes are explored, including a determination of the pairwise intersections of the different classes of models.
As always, it might be a good idea to follow up on papers that cite this one.
