First, you can't change the frequency of the external clock without physically replacing it. It runs at 20 MHz, and that's all it will run at. The problem with 20MHz at a lower supply voltage isn't power; rather, the chip isn't guaranteed to work correctly at that voltage and speed. (You can check the datasheet to see which speeds work at which voltages.) So, given that you need to lower the frequency, the easiest thing (I think) is to switch to the internal oscillator, which runs at 8 MHz. You'll have to do that with the fuse bits, and if you do it out of AVR studio, I think it's not that risky (I think there's just one option for internal oscillator).
As for the changing the clock speed in software at run time, I don't have any experience with that, but I suspect that it's not necessarily legit since the processor would try to run at the higher frequency until your code got executed, and that higher-frequency operation is what might fail. I don't think it's risky in the sense that you could brick your microcontroller, but it's annoying trying to debug code if you can't trust that it's being executed correctly. But, if that code happens right at the beginning of your program, I guess you would know right away if that part succeeded, and after that, you should be okay.