Batch rename sequential files by padding with zeroes

Question

I have a bunch of files named like so:

output_1.png
output_2.png
...
output_10.png
...
output_120.png

What is the easiest way of renaming those to match a convention, e.g. with maximum four decimals, so that the files are named:

output_0001.png
output_0002.png
...
output_0010.png
output_0120.png

This should be easy in Unix/Linux/BSD, although I also have access to Windows. Any language is fine, but I'm interested in some really neat one-liners (if there are any?).