One thing comes to mind that should speed up your search. Notice that the letters qw/c d j k m p q z/ do not appear anywhere in the words you have in the DATA. This means that the number of occurences of these letters depends only on the initial sentence beginning (the example you listed has only "three c's, three d's, one j, two k's two m's two p's, one q and one z" regardless of how many times the other letters occur).

With this in mind, we can group these letters and their counts to the beginning of the sentence (plus the "and" that appears before "z" plus the remaining letters themselves) giving us an initial sequence of:
"Any Perlmonk could write a sentence using three cs three ds one j two ks two ms two ps one q and one z . a b e f g h i l n o r s t u v w x y"
with only 18 letters left to match instead of 26.

Also notice that there is a minimum of number occurences for each letter. In our running example, "s" cannot appear less than 8 times (highlighted). This should make you start closer to the solution.

Also, "0 no" does not need to be there in the __DATA__ section because all letters exist at least once (in mentioning their names).

I hope these things help you find more solutions faster.