We (Braintree) support over 100 currencies: http://bit.ly/braintree-currencies . We're less hassle than other gateways, but getting merchant accounts for international processing isn't completely hassle free. It's more of an industry problem than a gateway problem, but we're working on it.
Spreedly? Or maybe that's a layer on top of gateways? I don't know much about payment gateways, so feel free to enlighten me on why it's not a solution to this, if it's not.
Spreedly is a layer on top of gateways, so it can only support currencies that the underlying payment gateway supports. Gateways that Spreedly supports: http://spreedly.com/info/payment-gateways/
And please make it implement digital receipts (see my suggestion below).
Amazon payments seems to be fairly non-sleazy.
But also decidedly non-international :(
what about google checkout?
Ugh, that's only for the UK and USA. If you're a Canadian and want to charge Canadian dollars to another Canadian it is 100% impossible.