If you are going to use an Android App then just use the Phone, no Arduino needed! It has GPS and Accelerometers so you can get actual distance and number of steps quite accurately and there are already several App out there that do this. I have compared a few and they show fairly close results