Really? Are there shops that don't take cards? I can't remember the last time I saw a shop in Atlanta that was cash only. Even tiny convenience stores in the really bad parts of town take cards.
If you use ATMs with any frequency, you need to get a free checking account and debit card with a bank* that will refund your ATM fees each month. Once you have one, the higher the ATM fee, the better you feel.
(*I use Schwab, particularly because it refunds ATM fees internationally. In general, just about any online bank -- e.g., Ally -- will also refund fees at least domestically. Many credit unions probably do this as well.)