The formula seems to be volt*5.9-6.6=mhz (valid between 1.8v and 4.5v), so at 3.3v, this would give 12.8mhz. Be aware that, if you are running at 12.8mhz, ANY drop below 3.3v MAY cause problems (and very hard to diagnose, too!) or you MAY get away with it.
However, Arduino Atmega328p chips have a "brown-out" detection set at 4.3v - any drop below that, the chip shuts down. You can get an ISP (AKA ICSP) to change the fuses - go to http://www.engbedded.com/fusecalc/ to work out what to set fuses to. You can also use the ISP to read the current fuses, or indeed reprogram the chip without an Arduino board - all my projects have a 6-pin header. If you do this, before reprogramming using the Arduino board, you will have to "Burn Bootloader" (in the tools menu). Note that programming can still be done via Arduino IDE.
Alternatively, if you want to go "light" (and have an ISP), you can change the fuses to use the internal 8mhz clock - this frees up 2 extra pins, too! Be aware, however, that the internal clock may drift 1.2 hours per day (=5%), compared to 1.7 seconds per day (=20 parts per million) on a typical quartz crystal. If you don't use it for timekeeping, this probably doesn't matter.
You will need to make changes to the timing, for your code - you need to add a boards.txt with correct settings for your chip/clockspeed etc - you can copy the settings from the entry for the board, change the name, and change the setting "build.f_cpu"; restart (or start) your Arduino IDE, go to "Tools->Board" and select the board you added.
You can move the chip on/off the board, and reprogram it there (note that the board selected in Tools->Board is the FINAL board, not the programming board). Be careful plugging/unplugging it - eventually, you WILL bend the pins! Alternatively, you can use ISP (ICSP), as mentioned above - much recommended. ISP programming will also work if the chip is factory default, so long as it has a working clock.
How much power is used by the chip depends hugely on what you do with it - not just clock speeds, clock source, etc but also sleep modes. If you are sleeping a lot, it may draw less when running faster than running slower - if almost all your time is asleep, then the power consumption should be counted per clock cycle, not per second - if your clock is half the speed, and half current, then you draw the same current per instruction. Since the rest of your time is spent asleep, you get no benefit. See http://www.gammon.com.au/power for a very good breakdown of power usage, tips on how to save power, etc.
If you slow your clock down too much, serial and i2c may become unreliable (unless you slow down the speed), but I would expect to be able to go down to 1mhz before this to be a problem - a 1mhz chip trying to do 9600bps has 104 instructions per bit of data transferred. i2c runs at 100khz, so you get 10 instructions per bit (at 1mhz) - possibly pushing it. 8mhz should be fine. Test, test, test.
There are 3 possible settings for the brown-out detection - there are 3 possible values for the AtMega328p: disabled, 1.8v, 2.7v, and 4.3v. I was under the impression (above) that Arduinos were normally set to 4.3v; apparently that is not the case (see comment below). I recall seeing somewhere that there was brownout detection. This is something to keep in mind, if your arduino resets, especially when putting larger loads on the battery (running motors, multiple leds etc).