I don't think you have much choices if you want to detect minimal movement. The gyroscope/accelerometer sensor is the way to go. Even there you need to add some filtering, since the accelerometer has some wavering.
GPS is not nearly accurate enough to be used to notice movement from table to hand.
Monitoring the proximity sensor might be of some use, but anything blocking that triggers it, and it really does not tell you if the phone is moving.
If you want to consume a lot of battery, use the camera. Stream some input through a filter, which determines if the image is moving.