Arduino and LEDs Power Supply Question
My suggestion is to create an external supply that feeds both the LED strip and the Arduino separately, and then decoupling the Arduino from the LEDs using power transistors or (better) integrated drivers.

But the use of a battery depends strongly by the use that you are going to do of the LED strip: if you are going to use the whole - let's say 9 A current (that is much) consider that a 9000 mAh battery (that is BIG) would last one hour.

Maybe a laptop battery or so could fit but still don't expect to use it for a long time.