I personnaly think the best would be if each store could act as a bitcoin bank. Basically you would have a bitcoin account in the shop, and you'll use with conventionnal banking-like transaction for every day purchases. You would only transfer bitcoin something like say one in a month, just to fill up your account. Such accounts could also use David Chaum's digital cash, so that stores could act like private money issuers.
Most stores offer some sort of gift certificate, gift card or store credit. You just need to convince the store to accept bitcoins for store credit.