I'm working on the display now. It won't require any hardware modification for now.

Distance calculation

I'm going to trust the speed the Arduino thinks it has : I know that the treadmill starts at 0.5 km/h and I know when the speed is modified, at least when it is changed by the Arduino. So every second I can add a certain value to the total distance, depending on the speed.

I'd prefer to avoid using floating point arithmetic in the Arduino code, in the end, it's just a 8 bit mcu!

So I'll count the speed in tenth of kilometers

// speed are in tenth of km/h
unsigned int maxSpeed = 80;
unsigned int minSpeed = 5;
unsigned int currentSpeed = 5; // the initial value is the speed of the treadmill when it just switched on
unsigned int speedStep = 1; // the step it increases/decreases every time we push a button

and I also need to know if the treadmill is running or not, I'll only update the distance if the treadmill is running

int treadmillRunning = 0; // 1 if the treadmill motor is on, 0 otherwise

Then I'll store the value in an unsigned long, because int are only 16 bits on Arduino, and I'll call the update function every second with a timer :

unsigned long totalDistance = 0;

void countDistance()
{
if (treadmillRunning)
totalDistance += currentSpeed ;
}

I'm using this library for timers : http://playground.arduino.cc/Code/Timer

Display

How will I display the data? On Linux desktops I'll use the Freedesktop notifications. For example here is the result with notify-send from the libnotify-bin package

Calories

I found a formula on Shapesense :

CB = [0.0215 x KPH³ - 0.1765 x KPH² + 0.8710 x KPH + 1.4577] x WKG x T
CB = Calorie burn (in calories)
KPH = Walking speed (in kilometres per hour)
WKG = Weight (in kilograms)
T = Time (in hours)

Once I get the distance right, it should be easy. It will be calculated on the PC, not on the Arduino, so you can easily enter your wheight/height parameters in a config file.