Zebstrika Replacement and Pseudo-Leg. Locations

I have a Zebstrika on my team, and I was thinking of replacing it with Delta Weezing, as it has more coverage and, with a good nature, it can be a special attacker. That brings up the question of: how can I find a pseudo legendary of any kind with relative ease to trade for DW? I tried fishing for Dratini, but I didn’t even find it once. I tried Safari Zone hunting for Deino, but the ones I found ran.
Is there an easier way to do this, or do I have to beat the 6th gym for the second “slot” for the friend safari and get Sliggoo or something from there? Or, should I just keep Zeb?

You can get a dratini in Roggan Town Game Corner. Otherwise, it would likely be while till you get a pseudo-legend (safari zone deino is pretty accessible as you can get more than one, might be missing a pseudo, but encounter rate is pretty low). So yea…