Do you have an objection to using a standard gateway and merchant account? Your bank may resell Authorize.net, for example (I know Wells Fargo does), which has pretty much everything you're looking for. You will end up paying about $40/month in fees for both of these services.
I have used Google Checkout as a payment service as well, and it works fine.
Intuit has a merchant account offering out as well.
You should probably consider Amazon's "Flexible Payments Service" too... I'm a fan of most of their web services. Not sure offhand whether payees must have an Amazon account to pay or not... but AWS services tend to be well documented:
Take a look at SagePay. I haven't developed against PayPal or GoogleCheckout but the SagePay documentation from the knowledgebase is pretty good. SagePay also have a neat little testing platform.
They have an easy to use API and they also provide different ways of payments. They also provide a service to let your customers pay by invoice and let you get your money immediatly so Klarna takes care of actually getting the money.
I'm a developer at Payjunction, so I recently looked at ActiveMerchant for Ruby (it can use Payjunction, PayPal, Authorize.net, and some others). If you are looking for a Ruby solution, I like their code, independent of who you use as an actual payment gateway. Don't have a recommendation in Python.
Stripe fits a lot of your criteria — you can accept credit card payments without a merchant account. You also get to control the payment flow without having to worry about PCI compliance.
A clean and well-structured REST API
The API is based entirely on REST — you can even use curl to charge cards:
Good example API implementations, preferably in in Python or Ruby
Stripe has official libraries in Python, Ruby, PHP and Java, and there are more community-supported ones here: https://stripe.com/docs/libraries
Worldwide credit/debit card coverage
You can charge all international credit and debit cards with Stripe.
Rates cheaper than PayPal (or the possibility to chose a payment plan)
You pay one standard rate of 2.9% + 30¢ per transaction. Unlike PayPal, there's no extra charge for American Express or international payments. Details here: https://stripe.com/help/pricing
I am an engineer at Stripe. Feel free to drop by our chatroom if you have more questions. You can also email us at support@stripe.com.