You don't actually need a Pokemon with this ability already. You just need skill with the Dex Nav and a large amount of luck. It took me forever to catch an Adaptability Skrelp, but I eventually got there.
I assume you are looking on Route 116, which is where Eevee is located. Past that, it is simply luck-based. I think (but can't confirm) that a higher search number will increase your odds of getting an HA Pokemon. Your Dex-Nav will display a question mark next to the ability on the info screen when it is the hidden ability, much like it does for egg moves.
So from the sound of it, you aren't doing anything wrong, you just haven't gotten lucky enough to find one yet. Aside from that, you might be able to trade for it? It is quite an in demand Pokemon for competitive use. Most people who breed Pokemon for wifi battles will probably have a few they don't want. I'm pretty sure I have a box full of them on pokebank myself.
Good luck with it, but from what I can tell you aren't doing anything wrong.
