ppumkin:
In research i came to the conclusion that using Lithium Polymer would be the best battery for long term power- am I correct? and using a single 700mAh LiPo could technically last to 5 years. Is this lifetime of a battery even feasible?
We haven't had any projects run for years yet, but it's feasible, and I know of others that have. If you use rechargeables, you may lose some of your battery energy just due to normal discharge over time, regardless of whether the Arduino is drawing power. LiPo/Li-ion is the best option in terms of energy density, but if you don't care about size/weight, other options might do the trick for less money. 700mAh isn't huge, so you have options.
Keep in mind that if you're using a standard Arduino board there will be other components on it that are always drawing power, such as the voltage regulator and FTDI chip. To get maximum power savings, you'll have to use a custom board.
We've been working on compiling info on sleep modes on our site and just posted our first article on the topic, you can check it out for more info: http://www.engblaze.com/2011/10/hush-little-microprocessor-avr-and-arduino-sleep-mode-basics/
ppumkin:
The second part is- Is it possible to store simple small integers inside the Arduino non-volatile memoery somehow to avoid keeping it in RAM and using power?
Yes, with a bit of additional work. You can use PROGMEM or EEPROM to store data long-term, they're both non-volatile: Arduino Playground - EEPROM-Flash. However, if your chip is sleeping but still on in order to record ticks from time to time, you can still use RAM.