As far as I can tell, virtually all UK banks issue Visa Debit cards nowadays. Certainly Halifax, HSBC (First Direct), Natwest, Santander, Lloyds and RBS do which covers most of the population.

In the past a lot of cards were Switch, which became Maestro and then everyone dumped it for Visa.

Fortunately we still have the Link system where you're not charged for using an ATM that doesn't belong to your bank. cough Canada cough.