In addition to what Flow says, and I think this is a superior solution:
Use application-specific passwords
The idea here is that you can create an application-specific password for any non web-based application that needs your Google credentials (think Android phones, mail clients, IM clients, etc.) You create a credential for each purpose and use this instead of your Google password -- this doesn't require special cooperation by third-party application developers. You can keep track of all issued application-specific passwords, and revoke them on a case-by-case basis if necessary. So if your phone is stolen, you can easily revoke access to your Google account and the attacker will no longer be able to log in as you. Please note that some applications might leave behind contact lists and offline email which will still be on the device even if it's not associated with a valid Google account. You'll need a remote wipe application for this purpose.
You can find this on your Google Account settings page. Look for authorizing applications and sites, and take it from there. See also this video from Google about 2-step authorization and application-specific passwords.
While at it, enable 2-step authorization using your Android device for an extra layer of security when you log in from an unknown computer/device.