For those who have updated to the latest version of google-play-services_lib and/or have this error Google Play services out of date. Requires 3136100 but found 2012110
this newer version of com.google.android.gms.apk (Google Play Services 3.1.36) and com.android.vending.apk (Google Play Store 4.1.6) should work.
Test with this configuration on Android SDK Tools 22.0.1. Another configuration that targets pure Android, not the Google one, should work too.
...
Execute this in the terminal / cmd
adb -e install com.google.android.gms.apk
adb -e install com.android.vending.apk
Restart the AVD
I found this way to be the easiest, cleanest and it works with the newest version of the software, which allow you to get all the bug fixes.