Argh pirates!
When you follow the steps to change your gamertag (for the 2nd time, with money) and you only get the option to pay with a Creditcard you might want to change the Microsoft website language. I live in Holland and only got the option to pay with Creditcard, after changing the website language I got the option to pay with Paypal too!
I hope this might help someone else too because I couldn't find any information about this, and I almost bought a creditcard just to change my Gamertag.
See you on the high seas!
p.s. Excuse my English