You can't beat Bootfairs.
They may not have the latest stuff and be full of loads of rubbish but it's full of really intersting people. There is little to beat the thrill of rummaging through endless boxes of CDs and finding an album you've wanted for ages, or finding a stall holder who likes the same music as and gives you advice. I met a guy who mixed a dashboard confessional album that i bought off him (i'm not sure if that's classed as cool on here but i think it is).
Also it's cheap, ican't afford record shop prices.
Saying that there are a few shops i like to wander around wishing i
could afford to buy all the stuff i want and find new stuff i've never
heard of before and wished i had it:
Plastic, St Albans- it's this really cool vinyl shop near me that sells
loads of DJing stuff and hip hop that i have no clue about and some
indie vinyls
Both the rough trade records - they fell really nice to be in and i love
the little cards they have that tell you about certain albums and stuff,
also they are both cool areas
The Picadilly Circus Virgin Megastore - It's huge i keep on meaning to
brave the Jazz section and buy some stuff