I have visa debit card linked with UK HSBC account. Are these cards widely acceptable in Iceland?
Whilst I've spent a fair amount of time in Iceland, and have a UK HSBC account, I tended to put most things on my credit card. I'm pretty sure that when I used my VISA debit cards I didn't have any problems. It does help to tell them that you are going abroad to make sure they don't block the card for suspicious transactions.
One thing that surprised me was that some places used chip & PIN, some places sign and some places (for low value transactions) don't bother with either.
I was on Iceland in September 2014.
You ask about Visa linked cards, but for completeness sake: I have used a Dutch 'Meastro' bank card (type debit card) on Iceland and it was accepted wherever cards were accepted. My Mastercard Credit card worked fine as well.
As Phil said, not always a pin was asked for, but mostly it was.
My wife and I were in Iceland in June 2015 and used our UK-issued Metro Bank debit card (MasterCard) everywhere, very successfully, right up until the point that it got cloned in a garage's pay-at-the-pump machine, and the bank rang us to cancel it.
The reason for using it was that Metro don't charge transaction fees inside Europe, so it was mildly annoying to have to start using a credit card halfway through the holiday (added 3.5% to the already non-trivial cost of everything).
In short: my debit card worked fine. I was glad that I had some other usable cards with me, though.