I don't know what's involved in changing the bootloader clock speed, so can't help you there.
I think that no fuses would need to be changed to go from 16MHz to 20MHz, so if the experiment goes bad you can simply put the standard 16MHz bootloader back on.
If you have the capability to burn a new bootloader (i.e., a programmer) you can burn sketches directly to the ATmega.
I think with Arduino 0011 the easiest way to change the clock speed in the code is to create a new board type (in boards.txt) and the appropriate parameters should propagate to the code.
-j