Building small, low-power pedometer/odometer with memory and time/date log
I actually worked on a bicycle data logger a bunch of years ago (Used to be called the Tune PowerTap, then was bought by Graber and I don't what happened to it after that), so I am familiar with the issues .

As you say, low power is key.  That means you have to do it right and not just grab a arduino just because that's all you know about.  Arduinos are microcontrollers with a some hardware and a lot of software sugar coating around them.  They are for people that don't want to know what is going on that just want to get a basic project working.  Many tradeoffs were made for the sake of apparent simplicity.  Ultra low power operation is one of them.  To acheive really low power operation and near zero power standby, you need to design for that from the start, both electrically and in the firmware architecture.  Physical size will also be a problem with a arduino.

It is unclear exactly what data you want to record.  It appears you are only interested in distance traveled, which can be measured in terms of wheel rotations.  The PowerTap used a fixed magnet on the wheel with a reed switch that would get close once per rotation.  That sounds like a good transducer for you too, since it takes no power unless you want it to.

Basically, you need only a small micro connected to the reed switch signal, a large EEPROM, a 32768 Hz watch crystal to keep real time, and some sort of communication interface so that you can get a data dump.  None of this is hard individually, but you need to wake up to design the hardware and the firmware architecture carefully to minimize power at every opportunity.  So my answer is, yes it can be done, but it will require more expertise to do right than it appears you are currently imagining.