Well, are the LED's SMD in the watch you have? I think they use lower mAh. I'm thinking of using 1 AA and boosting it to 3.3v - a bit clunky for a wristwatch, but it'll do. As to using an RTC module, an interesting idea, but I want to keep this project more simple (I.E., clock off the ATTiny). Battery life from the AA would depend on the draw of the ATTiny - boosting a 2000mAh 1.5V AA up to 3.3v at roughly 90% efficiency will give me about 900mAh at 3.3v to work with - just driving the LED's, that's a little over a month straight. I found some Surface-Mount green LED's that use 2.1V @ 1mAh, and I might be able to solder to them... hmm...
I've just been working on the actual charlieplexing part in EAGLE, and the circuit board layout is a pain.