I remember a movie scene where the guy kept his guns and some other go-bag-related stuff at a cigar shop that rented boxes in the humidor to customers.

Another option: some of the new temperature/humidity controlled storage facilities rent small storage lockers. Here's one such example that does a 4x5 locker.

http://www.fourseasonsselfstorage.com/storage_units.htm