You need the heat gun. A soldering gun is used for soldering large individual solder joints, and it's completely unsuitable for reflowing BGAs like the PS3 CPU and GPU.
A Ball Grid Array (BGA) is a package type where tiny balls of solder (hundreds in the case of a CPU or GPU) cover the bottom of the chip and connect it to the circuit board. Unlike most packages which have leads protruding out the side, the BGA can use the entire bottom surface of the package to make connections. Because the connections are very short, the inductance can be kept minimal and thus higher speed signals are possible. BGAs are great from a purely electrical point of view. The downsides are mostly manufacturing and mechanical issues.
BGAs are a challenging sort of package to reliably solder in the first place. Because the solder joints are under the chip, it's also difficult to inspect them. It's easy to create a latent defect which doesn't initially affect electrical continuity, such as a dry joint, pass continuity and functional testing, work normally for a while, and then suddenly crack and fail. Allegedly this is what is happening with the YLOD.
The idea behind the YLOD fix is to simultaneously remelt all of the solder joints, and in the process restore the cracked joint to working order. It may work, it may not, and it may just totally ruin the board. The key to having a chance at success is that all the joints have to melt at about the same time, so that surface tension can pull the cracked joint back together.
The heat gun produces a stream of hot air, which you can use to evenly heat the chip and melt all the solder joints at once. The soldering gun delivers its heat by conduction from a relatively small hot tip. This works fine when soldering a single wire, but on a BGA it just creates a single hot spot, cooking that part of the chip and melting the closest joints, while the rest of the joints remain solid.
First of all: modern PCBs use lead-free solder. It has a higher melting point and a different "look" when solid. Sometimes it helps to apply a little bit of lead solder to get a better heat transfer between the soldering iron and the solder joint. After the whole soldering joint is molten, I use a vacuum plunger ("solder sucker") to remove bigger amounts of solder. Remove the soldering iron to avoid overheating the component.
Then (the component wire is still in the hole) I use some quality brand desoldering wick: I place the desoldering wick in such a way that it has a good contact to the solder joint, and then press on top of the wick. This way the wick has a good contact to the solder joint.
About heating up the capacitor: It may well be that you overheated the cap, I'm not sure if the metal case is has a good thermal coupling to the contacts.
Best Answer
Of course, you can use aluminum as the nozzle, even though it's melting point temperature is low, I think aluminum alloy covers the upper limit temperature a chip can bear.
But why your heat gun has no nozzle?