I've been trying Piety and Honour starts this past week, including Shoshone, but really they quite suck. Honour isn't too bad if you can do lots of CS quests, and have enough barbs that YOU can kill (as opposed to the AI killing them) but Piety is really awful. It doesn't help you get a religion, so on the higher difficulty levels, whether or not you can get a religion and spread it is, as always, totally dependent on very specific map conditions, the CS you meet early, and your neighbours.
I'd argue that on Deity, in order to spread your religion to 10+ cities, you will need to get an early pantheon and/or faith wonder, AND have 2-3 neighbouring AI civs who have no interest in founding their own religion. Even then, those 2-3 can be spammed more heavily by the AI than you can do. Plus you have other stuff to focus on.
Religion is very underpowered in Civ 5 BNW. I hope they sort it out, and the Piety tree, by Civ 6.