To what fees specifically are you referring? If you mean things like low balance fees or overdraft fees I think they're both appropriate when they're not implemented or marketed in a predatory manner.
I'm not aware of any fees that are instituted "instead of the bank paying interest" unless you're talking about something like a low balance fee on a non-interest bearing checking account.
Most big banks in the US have monthly fees for keeping your money in an interest-free checking account. This ends up costing you something like $5-25/month unless you (a) also set up direct deposit with them or (b) maintain a minimum balance that is typically relatively large. This is why I keep my money with a credit union instead: better customer service, better rates, no stupid fees.
You can find free chequing accounts though and if you're careful enough to not get caught by overdraft fees, they're the way to go. I'm Canadian and I know 2 banks here that do it, but I'd imagine similar exists in the US?
Not all credit unions are immune to stupid fees. The "low aggregate balance fee" is alive and well locally. People wonder why Walmart is gaining popularity.
I'm not aware of any fees that are instituted "instead of the bank paying interest" unless you're talking about something like a low balance fee on a non-interest bearing checking account.