So, basically you want a cross between Genghis Khan and Muhammad?
This could easily happen under the right circumstances... Central Asia historically was a hodgepodge of Zoroastrians, Nestorian Christians, Buddhists, a smattering of Jews, Manichaeans, etc. before Islam showed up (and even for a long time after). All it would take is a local prophet to dream up some new syncretic evangelical faith and convert a powerful Kha(ga)n... Or for the prophet and Kha(ga)n to be one and the same. Really, pick a time, any time.
If you want something more specific - though not strictly in line with the parameters of the challenge (since it doesn't involve a *new religion) - I've always like the idea of a Manichaean Uyghur Khagan building an empire the size of Genghis Khan's and establishing Manichaeism as the dominant central Asian religion up to the present, maybe even converting China...