Arduino clock speed prescalers at start without fuses
I'm aware of the fuses, but those are pretty permanent

You can use the CLKDIV8 fuse, it only controls the preloaded cpu divider value so I don't consider it a permanent change.
The fuse sets the default loaded value to CLKPR (Clock prescale register) to either

clk/1
clk/8

Then in your code you can just set the divider to clk/1 to restore the cpu speed to 16MHz

I'm not sure but unless the bootloader is adaptive this change may affect the UART speed and create problems with the Arduino bootloader, this needs to be tested.

I did a test with my Arduino pro mini (m328p). After enabling the CLKDIV8 fuse using an external programmer, the Arduino bootloader becomes unresponsive and I don't see any way to override the UART speed that Arduiono IDE tries to use.

Updated Solution
I found another solution that doesn't need to change the bootloader, you just create a new profile for the board that has the CLDIV8 fuse enabled.
You need to modify the file boards.txt (e.g. arduino-1.5.5\hardware\arduino\avr\boards.txt), the baud rate for each board is stored there.
Locate the section that refers to your board, for example in my case
## Arduino Pro or Pro Mini (5V, 16 MHz) w/ ATmega328
## -------------------------------------------------
pro.menu.cpu.16MHzatmega328=ATmega328 (5V, 16 MHz)

pro.menu.cpu.16MHzatmega328.upload.maximum_size=30720
pro.menu.cpu.16MHzatmega328.upload.maximum_data_size=2048
pro.menu.cpu.16MHzatmega328.upload.speed=57600

pro.menu.cpu.16MHzatmega328.bootloader.low_fuses=0xFF
pro.menu.cpu.16MHzatmega328.bootloader.high_fuses=0xDA
pro.menu.cpu.16MHzatmega328.bootloader.extended_fuses=0x05
pro.menu.cpu.16MHzatmega328.bootloader.file=atmega/ATmegaBOOT_168_atmega328.hex

pro.menu.cpu.16MHzatmega328.build.mcu=atmega328p
pro.menu.cpu.16MHzatmega328.build.f_cpu=16000000L

Now copy and paste that section to create a duplicate entry that we are going to modify. In that entry you'll have to change the name so that it doesn't conflict with the existing one (any new name will do), and set the baud rate to 1/8 of the one that was originally used.
I'm showing the changes in bold

The old entry with the new one following it look like this in my case:
## Arduino Pro or Pro Mini (5V, 16 MHz) w/ ATmega328
## -------------------------------------------------
pro.menu.cpu.16MHzatmega328=ATmega328 (5V, 16 MHz)

pro.menu.cpu.16MHzatmega328.upload.maximum_size=30720
pro.menu.cpu.16MHzatmega328.upload.maximum_data_size=2048
pro.menu.cpu.16MHzatmega328.upload.speed=57600

pro.menu.cpu.16MHzatmega328.bootloader.low_fuses=0xFF
pro.menu.cpu.16MHzatmega328.bootloader.high_fuses=0xDA
pro.menu.cpu.16MHzatmega328.bootloader.extended_fuses=0x05
pro.menu.cpu.16MHzatmega328.bootloader.file=atmega/ATmegaBOOT_168_atmega328.hex

pro.menu.cpu.16MHzatmega328.build.mcu=atmega328p
pro.menu.cpu.16MHzatmega328.build.f_cpu=16000000L

## Arduino Pro or Pro Mini (5V, 16 MHz) w/ ATmega328 CLKDIV8
## -------------------------------------------------
pro.menu.cpu.16MHzatmega328CLKDIV8=ATmega328 (5V, 16 MHz) CLKDIV8

pro.menu.cpu.16MHzatmega328CLKDIV8.upload.maximum_size=30720
pro.menu.cpu.16MHzatmega328CLKDIV8.upload.maximum_data_size=2048
pro.menu.cpu.16MHzatmega328CLKDIV8.upload.speed=7200

pro.menu.cpu.16MHzatmega328CLKDIV8.bootloader.low_fuses=0xFF
pro.menu.cpu.16MHzatmega328CLKDIV8.bootloader.high_fuses=0xDA
pro.menu.cpu.16MHzatmega328CLKDIV8.bootloader.extended_fuses=0x05
pro.menu.cpu.16MHzatmega328CLKDIV8.bootloader.file=atmega/ATmegaBOOT_168_atmega328.hex

pro.menu.cpu.16MHzatmega328CLKDIV8.build.mcu=atmega328p
pro.menu.cpu.16MHzatmega328CLKDIV8.build.f_cpu=16000000L

After saving the file you'll see a new entry in Arduino IDE, by using it you will be able to program the modified board.