I go to the Diskery now and then, but a lot of their stock has been there for years and is a bit tatty, Music + Video Exchange is just up the road, and there are bargains to be had there, their pricing policy seem rather random! Hard To Find records is pretty close to there too, mostly dance music and they also specialise in DJ equipment etc.
If you're in the brum area, you have to try Polar Bear records in Kings Heath, they specialise in prog, death metal and krautrock, but they have bits and bobs of folk and ambient etc