It's going to be very hard to build credit without using credit cards. I really don't understand why people are so against them. As long as you are responsible enough not to rack up more charges than you can pay for, using credit cards can be very convenient. And if you pay your bill each month, it doesn't cost you anything more than using cash.
Having a checking account won't really help your credit. Your credit report shows your open credit accounts, with balances and limits, any delinqencies reported against you, and inquiries to your credit record.
I'm far from an expert on this but i just turned 20 a few weeks ago, and i have about $15,000 available in revolving credit accounts and a car lease in my name. Basically just from using my cards and paying them off on-time.