If you want to pay for your domain - you do not have to use Paypal, you can use prepaid Credit Cards (such as those available from FBC). Never having used one myself, I would advise you to ask FBC if you can transact internationally.
If you want a .com domain, I would strongly recommend a namecheap.com - there are sketchy registrars that disappear with your domain (and money) after 30 days (the registrars only have to pay after 30days, so they can fool you with the free [to them] 30-day sampler period)