Difference in bootloader of ATmega with 16MHz external crystal and 8MHz external crystal
Yes, the ATmega328 will run fine at 8MHz, at 3 volts.

The formulas for clock speed vs. volts are:


Below 1.8V - cannot operate
Below 4 MHz - use at least 1.8V
Between 4 MHz and 10 MHz you require: Volts = 1.8 + ((M - 4) * 0.15)
(Where M is Megahertz)
Between 10 MHz and 20 MHz you require: Volts = 2.7 + ((M - 10) * 0.18)
(Where M is Megahertz)
You can supply an absolute maximum of 5.5V


Plugging 8MHz into this formula: volts = 1.8+((8-4)*0.15) = 2.4 volts minimum (5.5 volts maximum). Note that, as batteries are used, their voltage goes down gradually, so the 0.6 volts difference will mean that your project will run a little longer.

Since your supply is > 2.7V, we can reverse the second formula: 3V=2.7+(M-10)*0.18); 0.3=(M-10)*0.18; 0.66=M-10, so you can run it at 10.66MHz at 3V (but it is likely to stop as soon as the battery starts to drain).

Your second question, I think, is the most relevant one - the bootloader is written for 16MHz, and some things will not work at other speeds - serial communications used for programming for example. The same, for that matter, applies to the program - if you put in a delay() instruction in your code, it will delay() for twice as long as it should.

You can get around the programming side by ditching the bootloader altogether - once your code is ready, select file->upload using programmer. This will still affect the speed your sketch runs at (anything time-related - serial communications, delay(), etc). To change this, you will need to add a custom entry to the boards.txt file. See [HOWTO:] Anatomy of the boards.txt file for custom boards.