I have a PPC6800 (Sprint Mogul), and with custom firmware does everything you want, except the internet is EVDO rather than 3G.

Another thought is to get bluetooth GPS rather than internal. Every cell provider has something that would work along those lines.