I guess it depends on the rating of your LEDS a bit -
But you will need to look at expanding the Arduinos digital outputs by using some latching Shift Registers.
Once you've worked out what rating LEDs your using you can get a better idea of what power source would be the best. If your just using standard LEDs (around 20mA) there's no reason you couldn't power the whole lot from a 9v PP3 battery, you could even use a smaller equivalent 9v battery to get the size and weight down - but the smaller you get the less it's life span will be.
I use an Arduino, 3 x 595 Shift Register and one of these Bi-colour Red Green LED matrix - the whole lot is powered by a PP3 9v battery and it'll last around 30 hours of solid LED scrolling fun!
Here's a video link showing my matrix if you're interested -
