Credit cards are a wonderful thing. Pay them off every month and there is nothing bad about them. My credit card interest rate is 9.9% so even if I can't pay everything, that rate is still lower than what some people pay to buy a car. The stigma related to them is the stupidity and lack of responsibility that much of America displays. I bet all airlines have partnered with a credit card company, just pick one. Compare several of them, sometimes you get get 40k or more bonus miles just for signing up. You get little perks like first free checked bag and priority boarding with some.
I always have the money on hand to pay off the credit card, I just use my credit card first to get the miles.