I don't know about other countries, but Rdio [0] is available in Canada. Which is interesting, since they have licensing agreements with the four major labels.
they just launched in australia, and unfortunately they seem to have a fraction of the library the US version does. Slowly getting there though. Zune Pass is here as well.