I hope it won't seem OP or unfair if my character has one of these? I have a legitimate history and reasoning for him having it, and that Poochyena would be inside it.
So, at RP start, he wouldn't have a Pokemon he could use. I might have him catch a few Pokemon, but he won't have a Dex. Will he fight in Gym Battles? Possibly.
That said, you could consider him a "Special Character" and possibly use him for plot purposes if you so desire.