What about another gargoyle Pokemon? It could be Rock, Rock/Flying, or Rock/Dragon, and they could appear at the top of certain buildings. They'd be lonely because they outlive most of their human friends/because people mistake them for sstatues and never go near them, and want people to interact with them. And they could be the next Voltorb: you interact with them, thinking they're just a statue with a PokeBall in its mouth. Turns out, it's a trick to initiate a fun battle for their amusement.
Stupid idea, I know. But I like it.