According to the help section on paypal's site, you don't need a credit card to sign up, at least for a personal account. I signed up for a business account just now without one. (Quite by accident, I assure you. Seems paypal and I disagree on what a "confirm" step is.) In my premier account I receive credit card payments and transfer them to my bank account often. What kind of problem did you have?
Here is Authorize.net's echeck page. Most payment gateways have echeck functionality now, but I believe most, if not all, require you to be signed up with them for credit card processing first.
Also some payment gateways also have functionality similar to paypal, where the user enters their credit card info directly into the gateway's form, which saves you the security troubles. (Authorize.net SIM integration comes to mind.) This thread discusses options for doing this.
By the way, please don't take this as an endorsement of Authorize.net, as I have never done business with them. They are just very popular for this sort of thing.
As for carts, I'm only familiar with oscommerce and zen cart. My personal opinion is that zen cart is much cleaner and easier to deal with. However, like I said before, you really should do a search of the board on this topic, as it comes up quite often.
