It isn't always a virus that gets into the phone.
A lot of apps carry adware/malware that **** with your DNS and are pretty much undetectable by any A/V scans.
Google cracks down on a lot of these apps but there are just so many so people are bound to get one eventually.