I use a three PAYG sim with the £5 internet add-on for 30 days, in a Nokia 6120 Classic. Works really well with my n800, and is really good value for money. This is internet (web and email mostly), not true broadband, but most things I've tried except VOIP work with it. Skype even works fine. You can also pay 50p per day with three.

I've not had any problems with coverage, except in the more rural parts of mid wales, and the speed is plenty quick enough.