How big/busy is your wiki? TMD offers cheap hosting plans,
here and a lifetime free domain name sweetens the deal. Compare your stats to
my wiki, and if you are near that or below, then I can say there shouldn't be any problems with using that plan. Don't expect much money from the ads, but if you want me to send you a referral from Kontera, I'll do that, they'll credit me $25 bucks. Which would be cool, and if we stay in touch, I'm thinking to some day get together with several small wikis and split the cost of a more expensive plan on a more powerful machine.
And to pay your initial server costs, you can use a credit/debit card, many will let you send a check/money order, and I'm not even sure about PayPal.