It seems that at least one place in London will do this at a price. They seem to have six offices in London and offer a postal service.
Disclaimer: I have absolutely no connection with this company and I have never used them. I just found it on the internet.
It appears that all central banks in the Eurozone will exchange notes indefinitely even when, as will happen with the 500 note, they are no longer issued. For instance the irish Central Bank states on this page that
The issuance of the €500 will be stopped around the end of 2018, when the €100 and €200 banknotes of the Europa series are planned to be introduced. The €500 banknote, like the other denominations of euro banknotes, will always retain its value and can be exchanged at the national central banks of the Eurosystem for an unlimited period of time.