Starting with Mysticism becomes progressively worse as you go up in difficulty levels. Firstly, the higher the difficulty level the more difficult it is to actually beat the AI to an early religion, because in the beginning everyone starts with pretty much the same ammount of default gold each turn (+9 from palace and base tile, and maybe one or two more from whatever tile you decide to work) but the AI gets progressively more massive bonuses to this value. So no matter how skilled you are you have pretty much no chance of beating an AI that also has mysticism to Meditation or Hinduism.
Secondly, a heavy early chop-rush becomes more and more indespensable as you go up in difficulty levels, and you don't need myscticism for that, you want mining and the wheel as your starting techs if you can get them. The only real way to beat an AI on the highest difficulty levels is to make big gains early on through a chop-rush fueled expansion or conquest. Either you'll be able to capture a holy city or set yourself up strongly enough to be the first to get code of laws or some later religion.
So, in short, you don't want mysticism on Emperor/Immortal/Deity game, so "yes" you can win without it.