Run into the closest water (or lay some down) or get on a boat -- water damages them too. So when they teleport next to you, they're being damaged from the water at the same time that you're hitting them with the sword. Firing a bow from a boat is the best idea if you're taking this strategy.
If you're not near water, run away and shoot at them with your bow. If you can, charge the bow fully, but charging the bow slows your movement. This tactic is less effective in water because your movement speed is reduced.
If you have to engage them with your sword, jump up and hit them on the downward fall of the jump. This will give you a critical hit with your sword, and so help you kill the Ender Man quicker.
Be prepared: full armour, bucket of water, full hunger meter and a good sword!