Lots of good advice in this thread. I've recently replaced few caps in an atx PSU (also electronics is my other hobby) so here are my 2 (euro) cents.
Although a desoldering gun is not necessary it is a great item to have. I have a Chinese desoldering "station" zd-8915. When I was recently replacing those caps on a very tightly packed psu I was glad I have it. I just applied extra leaded solder with a soldering iron first. Then I used the gun and finally I pulled the caps straight up the whole removal process taking less than a minute.
My "normal" method of desoldering without one is to heat/flow one leg and move the component to a side so it lifts on the heated side. Then the other leg is heated while pulling gently. This is very difficult to do on a tightly packed board.
Many people don't do the above, but use copper braid to remove solder instead. This works, but copper braid is not cheap in the long run (perhaps it doesn't matter for few caps). When using it make sure to free the cap leads/legs too rather than end up with no solder and the leg stuck to the side of a through-hole metallisation. Heating up a leg with no solder on to free it up can be frustrating.
These days I only use copper braid for removing excess solder on smd components when I apply too much.
If you plan to be doing this more often a desoldering station is a good tool to have (once you have a good iron).
As for temperature control I agree you need a soldering iron that controls its temperature in a tight feedback loop, but you don't really need a per degree temperature regulation. Eventually you'll probably use 3 settings. The normal (around 400C), a low (towards 350C), and a hot (~420-450). The hot and low being rarely used, but very useful when needed.
If you do end up buying a desoldering gun make sure to get one you can get consumables for in future. Tips use up pretty fast if you're desoldering a lot.
Also regarding bad caps in general it is useful to have a capacitance meter. Often if there is only one brand of caps used in a device and one or two goes bad I replace them all, but sometimes you have a mix of brands including some quality ones. Then a meter becomes very handy to check them (even in circuit in some cases). For example in that psu I had two 10v/1000uF caps that were bulging. They measured 15uF only! No surprise the psu acted weird (it switched itself off no doubt due to overvoltage/ripple).
Regarding replacing low voltage caps with higher rated ones, accepted wisdom is that it is fine, but it is worth to remember the lower the voltage of the cap the better the esr usually is (within the same type). So If you're replacing a 5V rail cap rated at 10V and all you have is 16V caps it is fine, but if you do have 10V and 16V caps it is better to install a 10V one, but the difference is very small.