You can view my solution. I think my solutin may be one of the fastest anwsers, though the code is a little bit much.

As you've determined, the trouble with considering all permutations only to pick the next smaller one in the set is that there are so many permutations with most of the larger numbers -- not to mention the inefficiencies of going between integral and string values. If we had ten digits, the number of ways of permuting those ten digits is 10 factorial (10 * 9 * 8 * ... 1 = 3,628,800 permutations when you only care about one -- 10 digits for the first, 9 for the second, 8 for the third... etc.). You don't need to consider all 10 factorial permutations to find the next smaller - there's a simpler more efficient way of getting the answer.

So try these suggestions:

1. Can you develop a scheme simple enough to do by hand for numbers that are less than 10^6? Maybe start with something even smaller -- let's suppose you had 7210, if we progress to the smaller numbers, 7210 -> 7201 -> 7120 -> 7102 -> 7021 -> 7012 -> 2710 -> 2701 -> 2170 -> 2107 -> 2071 -> 2017 -> 1720 -> 1702 -> 1270 -> 1207 -> 1072 -> 1027 -> -1 (previous was smallest without putting 0 as leading digit)
2. Try to understand the patterns at play. For instance, I can look at a number and easily spot when it's the smallest number. How do I do it?
3. If you spot a pattern, try to work it into an inductive/deductive scheme -- i.e., bigger picture from your simpler findings or the reverse if you happen to spot a larger pattern. Maybe you noticed something with 2 digit numbers that you can extend to 3 or more digits.
4. When you craft another potential solution, test that both it and your inefficient (but intuitively correct) version give the same results for small problem sizes (you don't have to stick with the sample problems, you can make your own).

Once you get it, the algorithm isn't significantly more complicated than the one you already have, but it will perform much better. When you find the solution, celebrate -- but don't lament that it took you as long as it did.

I hope this is enough to get you unstuck and that you're not too frustrated to give it a go.
Cheers!