I'm actually surprised if it's legal for a bank to refuse to provide cash withdrawals. Unless it's a case of "we'll do this now, because we have to, but we're also closing your account since we're allowed to choose out customers and your business isn't worth the hassle for us."
That's a very good question. I was thinking of legal tender laws, which I understand to usually stipulate that any debt incurred must be payable in cash money issued by the relevant state.
Of course, there are a number of ambiguities there, so maybe it is possible to run a bank without providing cash withdrawals and still be on the right side of the law in the US.
BECU (Boeing Employees Credit Union, WA State) only has tellers handle cash out of their main office, in Tukwila. Every single other "branch" is a Service Center with ATMs. They will help you get a loan or print a cashier's check, but send you to the ATM for any withdrawals.