God, I hate adware. I read at least one of you is rooted. Hate to say this. But, depending on where you got the files to root your phone? You may have been infected then. Yep, it happens. There are some evil idiots out there inserting this code. Only get your root files from the Dev that created it.
In the mean time. Since your rooted. You can try adaway. If both of you are rooted. Please try it. I'm guessing your host's file is infected. If so, adaway can clean it up. You won't find it on the play store.
AdAway | sufficiently secure
You can get it at link above. It does write to the system partition. That is a no no for play store rule's now. Has to do it to do its job. You can also back up your original host file too.
So, just a suggestion. Try it if you like. Or not. But, if you have tried all the other ad apps and their not finding anything? May be your last resort before a factory reset. Good luck.