How about running copper tape around the steering wheel and turning it into a capacitive touch switch? It assumes a particular driving habit, but at least it would be easy to implement.
Another solution could be FSR on gas pedal.
Can you add a magnet to the rim? (something like a window Reed Contact). Everytime the magnet travels by the Reed will switch.
You could read motion with a hall sensor. You need Unipolar or Omnipolar (Bipolar and Latching won’t work)
IR emitter and detector pairs with a reflective element on the wheel - but I guess in the desert it will become unreliable
Photointerrupter when you can attach an encoder wheel
Depending on the car, maybe take an analogRead of the throttle position sensor? A little less reliable than GPS/physically checking the wheel for movement but you’d still get a fairly accurate determination of whether someone is actively accelerating versus idle/stopped.
Make a DIY vibration sensor, aka two wires that bump together and apart, and just measure the how-much-they-bump. Or cut two long strips from an aluminum can and nail them to a board so they brush together when jostled. Or maybe a piezo speaker can be used in reverse as a vibration sensor?
Just measure the battery voltage or current draw from the cigar lightener.
I’ve seen a device vorking as a fm transmitter to the radio. Sending out some cool sounds depending on the RPM of the motor. “Just” measure the pulses and you know it
I am with Simon - grabbing OBD (or Can Bus) is relatively easy - you can get an OBD interface from Ebay for $10-20. This is a good source of instant info: http://forum.arduino.cc/index.php?topic=95037.0