I don't know for sure if this would actually work or not but it's an idea I had to register ccTLD domains in countries that require you have a local address.
If you create an account with Aramex global shopper then they give you a postal address in loads of countries around the globe (including the U.K). I would imagine that one could use these addresses for domain registrations as well - I have yet to try it out though... so if you do give this a shot then let us know how it went.
Postal address in not enough - i found a company but they wrote me that -
Rights of registration will be reserved for the owner of the .co.uk initially for 5 years. You will need to be the owner of the .co.uk extension to qualify for the .uk extension.
Postal address is not your problem to register .co.uk. You can use your country's home address to register .co.uk and you will only need to validate your address with either photo ID .i.e your traveling passport, national ID or driver's license or utility bill and within few days you are done with the validation and you are good to go with your .co.uk domain.
But if you are interested on .uk, that will require you to have a UK administrative address. However, you can not have .uk domain without having the .co.uk which is the first step for you to reg .uk domain of that same name which you have the .co.uk