Posting this in case it's useful for other NZ and AU hobbyists.
Being new to Arduino I quickly learnt about the fact many(most?) USB power banks have a low current cut off, making them not very useful for small Arduino projects. I hadn't found too much info on specific brands or models that didn't feature this other than products in America that were possibly discontinued, or reasonably pricey.
In my searches I saw Kmart (NZ, not to be confused with the US version?) had $10 3350mah power banks. Given the price I figured there was nothing to lose and that being so cheap they likely wouldn't have any extra bells and whistles.
I was right. These banks will supply power continuously to an arduino even if nothing is running other than the power LED, and will do so for days on a single charge.
They're fairly compact (not much longer than an Uno) and rubberised. Have survived my toddler throwing it around a fair bit whilst attached to a gadget I made him.
Link to the charger: