I was a bit scared about doing this but it was really easy and thought I would share my experience.
Step 1: Gathering the Parts
I found the cheapest atmel 328p (the same as was coming out of my arduino, with the arduino bootloader preloaded on it) on ebay, buy it now from the UK so I would have it as quick as possible so I could continue with my arduino powered project (await future instructable ;) )
Total cost: £5.90 delivered next day
Step 2: Removing the Old Chip
I gently wedged the bar under one edge of the chip edge, not the edge with the pins mind (I still plan on fixing this chip)
I wedged it then on the opposite side of the chip. Neither not enough to pull the chip off just to loosen it off uniformly.
The when both were loose I wedged the bar under it again and this time twisted to pop the chip up, then repeated again on the other side.
Now the chip is free to remove with your fingers.
Step 3: Inserting the New Chip
I carefully pinched the pins together with my finger, not enough to match the same as the old pin but straight down so when I push the new chip into the board the board bent the pins into the correct place.