I'm from Canada. Used a US VPN (TunnelBear), connected to music.google.com. It asked for credit card info, I used my own CC#, but when it asks for an adress I used Microsoft's name and zip code. It let me register and use google music. That was a 2-3 months ago, never had a single issue using it afterwards without vpn.
When Google Music All Access went live last week or so, I went back to music.google.com, accepted the trial. It asked for CC# confirmation, I re-entered Microsoft and their head office's zip code, and it logged me right in, no VPN required.
Now, I'm not sure yet if yes or no they will process payment on my credit card in a month when renewal starts, but so far so good.
Try it, it's a great service.