Well, the only device using debian packages where navigation makes sense is N9, you will find all the features you mention there. I leave it up to you to search for a debian packaged barcode/qr-code scanner there, see if you can find it yourself.
As for desktop debian you should check out Marble, it is already competitive with Google maps where I live, and I believe it is ported to N9/N900 and can give you off line maps. http://edu.kde.org/marble/
Quite astonishing when it has had little to no funding, and everything including maps is free.
As for Qr-code, did you know that generating qr-codes is built into the clip board tool in KDE, so that you can generate a qr-code out of everything on the clip board with a click? One of hundreds of useful features I miss on any proprietary desktop.
Keep an eye on plasma active. With little funding, no devices, it still already is quite capable. If devices with it comes with GPS, you can expect work on free navigation software to catch on. I do believe devices will come with camera, so I am willing to bet that barcode/qr-code reader will follow at some point if it is not already there. And yes plasma active is already distributed by kubuntu as debs.