If you go to the gym often take note of who the regulars are and their general abilities. You aren't going to know everyone's name but you might get a rough idea of their capabilities. This will give you introduction lines like:
I haven't seen you around here very much. Are you new?
I noticed you mostly stick to bouldering. Last week this lady almost dropped me. Do you mind if we run through a quick refresher together?
I noticed you have been working XYZ route with your partner. Just incase you haven't seen me belaying people do you want me to demonstrate my belay technique?
###Experienced doesn't mean experienced with a GriGri
Experienced doesn't mean experienced with a GriGri
I climbed for quite a while before I handled a GriGri. Instead of asking if they're experienced, ask if they're experienced with a GriGri. In the comments David Richerby nicely expanded this idea:
Asking "Are you experienced in [this specific skill]?" rather than "Are you experienced in [this general area]?" is excellent advice for almost any situation. Don't assume that somebody who is generally experienced necessarily has experience with the specific thing you need.
###Ask to join a group instead
Ask to join a group instead
Scout a few pairs and notice how comfortable they are on belay. When you're comfortable with their abilities explain your situation and ask if you could join their group. This strategy admittedly works better if you're moderately social so you aren't walking up to them completely cold. I know I'd help out a friend in that situation.
Hi Erik and Ben, my partner couldn't make it tonight do you mind if work this route with you guys for a little bit?
###Look at their gear
Look at their gear
You can tell a lot about a climber based on the gear that they wear. Does the person have really worn shoes, and a brand new harness? Either the person just got a new harness or they've been mostly bouldering. Does the person have a harness with nut tool dangling on the back? Odds are the person is doing some trad climbing outside of the gym.
Roflo also added a comment about weight disparities.
I'd like to add that I've seen long-time belayers struggle when faced with a climber that's considerably heavier than they're used to. I even recall one guy saying something like "be careful, I'm heavier than I look" to every new belayer he met.
If you think you're a deceptively heftier person than the average you might want to consider mentioning it. Ideally the belayer would be extra vigilant for those kinds of things with a new partner, but that obviously isn't always the case.