Im only sure on the below on Deadfrontier as i don't play evony anymore.
They of course have the paypal, credit cards, Debit cards, Onebip (SMS payment method)
http://www.paybycash.com/ is used also.
This site uses the following ways of payment (all are used without a credit card)
1. Ultimate Game Card (Main Option)
2. Boku - Pay by Mobile
3. Cash (through the mail)
4. Western Union QuickPay
5. Money Order or Cashiers Check by Mail
6. Check (through the mail)
7. Check (by fax)
8. TravelersExpress MoneyGram
9. eCheck (one-time direct debit)
At Walmart there are stacks of the Ultimate Game Cards they sale very well. Sometimes they are out when I want one lol. They sale at gas stations too.
I'm not sure what it takes or how much it cost to add a payment option but there are games not as popular as TW that use it. I think it would be possible to add it and make profit.