To answer your questions :
1. The letter is the appropriate first step. you inform the flat owner over which you have a right of way and a copy to the landlord / freeholder. you state you right of free and uninterrupted use and refer to the right in the title deeds. you state that there is an obstruction which is interfering with your right and you want the obstruction removed within 21 days. If No action is taken you will have no option but to refer to the court for an injunction.
You can potentially emove the obstruction but do not mention this as the neighbour may sit back and wait for you to do it. I don't recommend this because if you cause damage you will be liable to make good.
2. send the letter to the address stated on the title document.
3. Unless there is an obligation in the title deeds for there to be a fence then you have very little chance of succeeding in getting it reinstated.
Any questions or queries?