Re: or you could go even more downmarket...
The famously amazing Victorian Gothic Icknield St library in Brum does not have wifi, there is a notice directing readers to the Tesco Cafe in the modern complex that you can walk through to. Reasonable speeds.
Upmarketish: Should anyone find themselves in Birmingham New St Station, look for the Coffee Lounge independent cafe just opposite the entrance. Fast wifi, no landing pages, wpa2 password is written in felt tip by the till, better than 1.5 Mbytes/sec mid morning when the hipsters are not in. I just do Americano, tastes fine, comes in a bucket, not too expensive. They do beans on toast as well as all the panini stuff.
Free connections across Brum centre: Plenty of cafes, chain and independent. Central reference library and the ICC both have free wifi. No encryption but you have to negotiate a landing page and that needs noscript disabled for the initial connection. Speeds around 120 kbytes/sec. Mobile connections (G3 is my limit) are variable across the city centre. Some places are effectively Faraday cages, others its rocking.
Outside centre: Midland Arts Centre (MAC) in Cannon Hill Park has free wifi again no encryption but (more sensible) landing page so you can agree terms &c. Around 800 kbytes/sec to 1 Meg bytes sec mid afternoon weekday. Holds up well at weekend. Nice place to sit outside within range.