There’s a good post over at MetaFilter asking about using GPS on bikes. The original poster was interested in a GPS solution to fight theft (LoJack on two wheels), which is still pretty impractical.
But the post does mention some interesting applications and products. There’s the Garmin Edge 305, a GPS with cycle computer and heart rate monitor in a unit small enough to strap to your stem (or its little brother, the no-heart rate Edge 205).
Addressing the original question, I found this article at Popular Science about using mologogo and a prepaid cell phone. I’m just not sure how you could effectively hide the cell so it doesn’t invite the theft the original poster was trying to prevent.