Modern phones, including Android, iPhone, etc. etc. etc. have this ability. Whether or not a given navigation app uses it is another matter.
You don't have to use wheel sensors or the odometer (did you mean speedometer?), although those are useful inputs.
A more applicable and general term than "dead reckoning" is "sensor fusion".
Here's what Wikipedia has to say about dead reckoning:
"In navigation, dead reckoning (also ded (for deduced) reckoning or DR) is the process of calculating one's current position by using a previously determined position, or fix, and advancing that position based upon known or estimated speeds over elapsed time and course."
But we can do better than that, today, and there are a number of sensors that - with the right math - can be "fused" to provide a more accurate estimate of position than would be possible using any one. GPS, then, is just one potential input.
Wikipedia gives a very broad definition, as this isn't just applied to navigation:
"Sensor fusion is the combining of sensory data or data derived from sensory data from disparate sources such that the resulting information is in some sense better than would be possible when these sources were used individually. The term better in this case can mean more accurate, more complete, or more dependable, or refer to the result of an emerging view, such as stereoscopic vision (calculation of depth information by combining two-dimensional images from two cameras at slightly different viewpoints)."
Phones today typically have GPS, accelerometer, magnetometer, and gyro sensors. While additional inputs such as auto speedometer (not very accurate, though, by law only required to be +- 1.5% or so) and wheel sensors might be useful, they certainly aren't required.
I'd assume that major navigation apps already do this, probably using Kalman Filtering:
http://www.cs.unc.edu/~welch/k...
http://en.wikipedia.org/wiki/K...
So, this is nothing new. But, then again - there's no claim that it is. (Just the incorrect reading between the lines here...) They've just conveniently put the needed sensors and a means of performing the calculations in a single chip.
You know, just like Apple did for the iPhone 5S...