If your main goal is to save power and be able to run at lower voltages then what you are looking for is ”CLKPR – Clock Prescale Register” which determines System Clock Prescaler for dynamic frequency scaling. It is initialized during reset with value of CKDIV8 fuses, but you can change it anytime during runtime. No need to avoid external oscillator or reprogram fuses every time.
Here is the excerpt from the Atmel datasheet:
The ATmega48P/88P/168P/328P has a system clock prescaler, and the system clock can be divided by setting the ”CLKPR – Clock Prescale Register” on page 377. This feature can be used to decrease the system clock frequency and the power consumption when the requirement for processing power is low. This can be used with all clock source options, and it will affect the clock frequency of the CPU and all synchronous peripherals.
CLKPR = (1<<CLKPCE);
CLKPR = 0011b; // Divide by 8
Of course, as it was pointed out earlier, any code that assumes CPU speed will be affected.
You can start up at medium speed, measure your supply voltage, and then either drop down to a lower speed if you need to conserve power or ramp up to a higher speed if you are connected to a host and power is not an issue.
I am not an expert on Arduino bootloader, but I believe you can configure it for default communication and then drop your speed when your sketch starts running.