I know of several large retailers that allow their employees to be paid via a debit card.

If you don't setup direct deposit before your first paycheck, instead of mailing you the paycheck you get a debit card. You can then withdraw the full balance out of it every two weeks without any fees.

This doesn't help with all of your banking problems, but it's a good start.