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.