I believe 3.7 volts is below the threshold for 16 MHz. Many folks have claimed that running a processor at 16 MHz / 3 volts works but it is outside of the Atmel specifications.
No. But the answer to the next question has to be "yes"...
Do you have a way to change the fuses?
I honestly have no idea what you are telling me? Could you restate it? I'm new to all this. I feel like your information is valuable and I don't want to miss it.
Do I need to use anything more than just the naked atmega328 chip?
I'd really like to use just the chip from my arduino uno rather than the pro mini. is this possible?
The bare chip needs to be loaded with a 8MHz boot loader and you will need a programmer for that.
The fuses can be changed with the programmer. You can see the fuses as the settings in the bios of a computer.
The fuse settings set things like if you use a crystal or not if the internal clock needs to be divided or not.
Do yourself a big favor & get a 2nd arduino - then you can keep your deumilanove intact for programming & development, and download into something like promini for embedding into your project.
A word of caution on those batteries... they may require a cut-off circuit to ensure they don't "run dead". It's my understanding that lithium batteries are damaged when they are run below a certain charge. I can't tell from the description if those batteries have an internal cut-off. From the comments, it appears most people use them in an existing device that presumably has a cut-off.
Mann.. there HAS to be an easier way? So I cant just use the external oscillator and the chip with an unregulated battery source??
Yes. You can either take a chance and run at 16 MHz (which is very likely to work) or obtain an 8 MHz crystal (or resonator). But you may have to change the fuse settings to adjust or disable the brown-out detector. Or, if you go with AA cells, just add a third battery.
Standard AA alkaline batteries typically have more total energy (2700–2900 mAh per cell according to Wikipedia). The draw-back to alkaline cells is the voltage drop (1.5 full to 0.9 dead). The benefit is the ability to run-dead and lots of energy per cell. I have a few gadgets running directly from two AA cells and I'm very pleased with the results.