I like the INS approach, but couple that with cameras to correct for random walk error (this is much like our eyes correcting for our inner ear.)
I think the issue with Google maps requiring GPS differentials for getting your trajectory has mostly to do with it being agnostic of your phone's orientation while moving.