Okay, so Matt and I saw a while back on The Screensavers that there was an MP3 service out there called All of MP3. It's based in Russia and it's border-line sketchy, but maaaan is it cheap!! I've already downloaded two albums and spent around $1 for both!!!
Now, as I said, it's borderline sketchy. But they do accept paypal, though that's down at the moment. So you can also get one of those 1 use credit card numbers for a pre-set limit and pre-set window of activity and use that (which is what I did). If you do that tho, be prepared for your credit card to possibly reject you until they call and assure that you're OK with transactions from Russia going thru on your card.