Hi Max.
to burn the bootloader you'll need additional hardware, like mentioned before in this thread.
Depending on your skill with a soldering iron, and if you have access to a pc with an old parallel port (eg lpt1); you can make a parallel ISP cable.
As described in the above link, you'll need to install "giveio" before you can use the parallel programmer to load the bootloader.
to load the bootloader on the new chip, simply unmount (pry off) the old ATmega chip, and insert the new chip (and make sure it is plugged in the right way!!)
Power up the board (via USB or other external power source, as the parallelProgrammer will not power the board), plug in the parallel programmer, and program the bootloader.
when it's done, you should be ready to program your arduino like you would normally. 