I'd say just forget about those travel cards. You sound like you're struggling to get above $300 in your checking. And, those issuers are pretty strict on mininum income for those with little or no credit background. They also charge hefty annual fees. Whatever rewards you're going to get is paltry if you don't charge a lot.

If you like travel, I'd say get yourself one of the student cards from AMEX. Build your credit. Eventually, they'll offer you one of their other cards. And, if you have already have a card with them, the minimum income requirement is waived.