If payments are an issue, maybe someplace like Ireland? There are well trodden paths here.
In the UK you can register a company online [0], however you need a UK address. There are various formation agents that will register the company and provide an address for a small fee (<£100) [1]. If you want a business bank account I think you'll need to do it in person though. You will probably want to get an accountant too which will be ~ £1k/year, although you can do it yourself.
Further reading:
http://www.bdb-law.co.uk/media/440379/settingupbusinessinthe...