With the fans, it depends on the case you have. In older cases, the fans were either screwed in, or were placed in plastic holders. With the holders, they just pop out once you push the tabs back, with the screws, you unscrew them.
For some fans in the newer cases, they're riveted, so in order to remove them you might have to drill the rivets. They're likely plastic so it shouldn't be an issue. You can put them back in with screws. The door fan is the most tricky. You can take the door off, then there are two or three screws that hold the plastic outer case on the metal door. Once you have the plastic off the metal door, it's easy to see how the fan comes out, and you can decide if you want to do it. With the outer plastic off though, you may be able to get into the fan and clean it without removing it. I use a small paint brush and canned air to clean my fans.
While you're in the case cleaning, take the fan off the cpu heatsink and clean out the ribbing. Surprising how much dust can build up in there...
As for the psu/vid card, 700W should be enough.
As for the pcie 1.0 vs 2.0 issue, not sure how that'll affect performance. If it's really a problem you can look into getting a newer motherboard. Cheaper than the vid cards usually, but a lot of work to install since you need to take everything apart to install a mobo. Once you've done that though, you'll be much more comfortable tinkering inside the case.
I'd go ahead and test the new card in your current system, and try to clean the fans without removing them. Chances are that'll work out fine.
