Nice puzzle! Let's see...

None of the digits can be larger than 5, because 6^6=46656, which is not a 4-digit number.

The digits can't all be 5, because 4*5^5 is too large. There also can't be 3 fives, because then the sum would be >= 9375, and there can be no digits larger than 5 in the right-hand side. There also can't be 2 fives, because then the sum would be >= 6250.

There can't be no fives, because four fours would give a sum of 1024, which is not a solution, and anything with no fives and less than four fours gives a sum of less than 1000, which is not a four-digit number. Ergo, there must be exactly one five.

The remaining three digits must all be less than five, so the sum of the powers can be no more than 5^5+3*4^4=3893. One five and three fours isn't a solution. One five and two fours gives a sum of >= 3637, which fails because the second digit of the sum is always too large. So there can be at most one four in the solution.

Given that there must be exactly one five and no more than one four, the sum of the powers can be no more than 5^5+4^4+2*3^3=3435, which happens to be a solution. The lower bound on the sum of the powers is 5^5=3125, so the first digit of the solution must be 3.

Given that the solution must have one five, at least one three, and at most one four, there are two groups of potential solutions: five, three, and two digits <= 3, and five, four, three, and one digit <= 3.

In the first group, with a five, at least one three, and no fours, the sum of the powers is between 3152 and 3206, so the second digit can't be a 3, so there are at most two threes, which lowers the upper bound of the sum to 3183, which means there must be at least one one, which lowers the upper bound of the sum to 3180.

So, the solution must have 5, 4, 3, and one digit between 0 and 3, or it must have 5, 3, 1, and one digit between 0 and 3. Out of those 8 potential solutions, only 5, 4, 3, 3 works. That's technically still a brute-force answer, but brute-forcing among 8 solutions is better than doing it among 9000, I guess. :-)

*Edited: 29 May 2011, 3:30 a.m. *