@ Unknown_K: I have no idea where to get stuff like that locally. There are some shops that'll do the work for you, as there are for repairing the BGA GPU on defective iBook logic boards. I'm not willing to pay for it, though.
Reballng kits with a proper stencil for the part you're reballing can easily cost in the $400 - $700 range. For example, this kit:
http://practicalcomponents.com/tools_supplies_training/bga-reballing-kit.htm
costs $650. Of course it comes with enough solder balls to reball hundreds of chips. It's not worth it if you're only going to do one or two, unless you're doing it for a wealthy client. However, there are less expensive options available on Ebay without customized stencils (you tape off the unused holes). But those Ebay options are still about $300 once equipped.
After you have the balls properly positioned, you still must heat the part with hot air or bake it to attach the ball to the part. Otherwise when you turn it over the balls are likely to fall off.
BGA soldering is probably more easily done with a customized toaster oven, than with hot air, but either way will work and both methods have ads and dsads which vary depending on your experience level.
The tricks to BGA soldering are component preparation, using good flux on the board (esential), proper (registration/alignment) placement of the part on the board and most importantly, a usable thermal profile. The thermal profile is how long the part and board spends at each temperature.
For one or two parts it probably is cheaper to pay a professional shop, and it will cost at least $75 and possibly $300.
It's not hard to change the clock frequency of many of the later models, particularly the Tanzania clone boards (which are designed for multiple 603/604 configurations) and Gazelle models: it's just a couple of resistors to change the clock speed. Much easier than trying to figure out the clock config on a PB 5300...
You must also double check whether newer fast CPUs use the same voltage levels as the chip you are replacing.
When I experimented with replacing the PPC601 on 6100 and 7100 boards I found that the original PPC601/66 or PPC601/80 ran on 5V, but the later PPC601/100 that I was trying to use expected 3.3V.
Jeff
P.S. A hardware store heat gun can be used as a source of hot air. However, it is desirable to control the heat level and the air speed. Home Depot used to sell a Milwaukee brand model with a continuously adjustable temperature dial on the back, I don't know if they still do. That would just leave applying a control to the blower, or living with the air speed which it uses.
Also, nearby parts can be masked with modeling clay, so you do not blow them off the board.