What To Do About Android Malware?

What's your approach to detecting and dealing with Android malware? I have a fairly new, fairly fancy phone running Android Lollipop, the recently degraded performance of which leads me to believe that it's infected with malware. That, and a friend who noticed a lot of strange activity coming from my phone's IP — sorry, I don't have the logs, but he pointed out that there were pings coming from my phone to a lot of sketchy addresses — which pretty much seals the deal. There have been lots of stories lately about Android malware that remind me of the old saw about weather: everyone talks about it, but no one does anything about it. However, that can't be completely true, and before I reach a phone crisis, I'd like to get some sane, sage advice about diagnosing malware, and disposing of it, or at least mitigating its damage. When it comes to diagnosing, I don't know what software to trust. I've heard positive things from friends (and seen both positive reviews and terrible negative ones, raising even more meta questions about trust) about Malwarebytes, so I installed their mobile version. This dutifully scans my system, and reports no errors and malware. Which doesn't mean there isn't any, though I'd be happy to find out that I'm just being paranoid. The OS is stock (Motorola Nexus 6) and kept up to date. I have only very conventional apps, all downloaded from Google's Play store, and believe it or not I don't visit any dodgy websites on my phone, at least not intentionally. So: what's the most reliable way to get an accurate view of whether I am dealing with malware at all, and hopefully to eradicate it? Good malware hides well, I know, but is there any tool on the side of the righteous that is currently best at rooting it out? If I find a specific form of malware on my phone, how can I remove it?