With the little work I've done with Amazon Flexible Payments, I had to redirect to Amazon as well.

Although not free, cheddar getter will probably be cheaper than brain tree.

There are also some paypal functions that even though they take users to the paypal website, you can send them to a php?get= page where you can store subscription values in your database. I did this for a project I was bootstrapping a while ago.