If you are in the UK with a UK bank account, you are going to need a UK gateway and merchant account - unless you relocate. It's just part of the "know your customer" anti-money-laundering deal that all western countries have between their governments and their banks that make it difficult to set up abroad. It might be possible, but it's just extra headache.
I would suggest looking at Recurly as your integration endpoint for a few reasons:
1) Multi-currency. Some people claim it's "expensive" as as $200/mo add-on, but the extra conversions from geo-targetting visitors with their native currency make this a no-brainer, especially for UK companies.
2) Data portability. You can leave Recurly in 5 years if you want to write your own recurring billing app or switch to somewhere else and they will give you your data.
3) Not having your customer's CC details held at the gateway (Recurly are best described as a value-add intermediary) means you should be able to easily switch out gateways later on. This is a key architectural choice that I don't think people pay enough attention to, and Recurly really don't promote it enough. Chargify etc do not do this, instead they store your customer's details at the gateway and have no power to retrieve them ever again.
4) Supports VAT.
The down side to Recurly is their API is a bit messy. Their hosted payment pages and "transparent API" appear to be next to useless if you want to also record extra information (e.g, username) as part of the signup process in a seemless way.
With regards to payment gateway, pick any payment gateway from here: http://recurly.com/features/payment-gateway-support
The truth is, it really doesn't matter. As long as it is working, and your bank/merchant account doesn't put a hold or delay on your income.
Don't stress about the transaction fees. People get too hung up on a percentage point, with the frame of reference that "when we've got $10m in revenue, that 1% is worth $100,000)", but honestly, when you get to that point, you will have enough business savvy to re-negotiate or look for a better deal then. When you don't have any customers, it really doesn't matter.