There are a lot more speakers in Cardiff than people give credit for - so I think you'll be surprised by where you find them. I've always had success in Cardiff with the "usual" spots, but then again I've also found Welsh speakers in "normal" places like Costa Coffee and Lush the soap shop.
Aside from having a number of Welsh schools in the area, anyone under the age of about 35 working in a shop who grew up in Wales will have had to do GCSE Welsh second language at a minimum, so even if they don't speak it, they'll at least have an awareness of it - rather than giving you a sort of look as if you were an alien.
It's different where I live, because in Ceredigion - there are a higher proportion of Welsh speakers, so I'll admit that if I get a knockback, I tend to go "Oh..?" whereas I think down South I would tend to go with a bit of a "OK".
Over the last few months I've been carrying my useyourwelsh.com fliers around, so anyone who gives me a "I don't speak it.." gets a flyer, whether thats in pubs, clubs, banks, shops or wherever