This is the gaping, whistling hole in the story. All those third party app stores require you to manually turn on installation of third party apps that didn't go through the Play Store. Guess how many Android phones there are that use those stores. Hint: It's very close to the number of those listed as infected.
Doing risky stuff (installing from cheap or Free Chinese app stores) can be risky, who'da thunk it?