I have never been charged a fee of any kind for any service by my bank, a small, locally owned bank in Fairbanks, Alaska. Those services include checking, savings, wire transfers to foreign countries, money orders, automatic monthly bill pay, electronic banking, overdraft protection, and a host of other services I don't remember or never needed to use. (I have used all of the services listed above)
My overdraft protection is not free, but there is no fee involved. Instead, I have a revolving line of credit so if I go into overdraft, the bank just covers the overdraft and I pay about 8% annual interest on the loan which is normally paid back within a few days so actual expense is trivial.
My credit union is the same way. Free checks, interest earned on savings and checking accounts, no fee outside of interest for overdraft, etc. They do charge for out of network ATMs, which is rough since the credit union is in UT and I'm in AZ. It works great for online payment though.