Don't use interrupts. They are no help for this problem and will just bring in a whole new layer of problems.
You can use the Arduino's internal clock to time things to the accuracy of the crystal/resonator. The accuracy varies depending on the type of board you have but none of them are especially accurate and certainly not good enough to provide an accurate timestamp over the long term. You will need an external clock source. You could get that from GPS, or from you WiFi network connection. Both of those options will need power. You could also add a real time clock module. That would take negligible power.