We don't give any specific recommendations, but you could use almost any other leaderboard service as most other than Google Play Game Services will function properly on AOSP devices.

As to your second question, you cannot request this feature. It specifically states so in the submission form. If you select Yes, your application will be rejected.

We do permit Google Play leaderboards IF your application does not prompt the user to login to Google Play upon application execution. The action must be user requested, as in they press the leaderboards button, never automatically or upon completing a level and so on. So that users with an AOSP device will never see a Google Play error message unless they press the leaderboards button on your main menu. Note though that use of Google Play leaderboards will prevent your application from being a featured app, or promoted in any channels such as Top New, etc.