If piety doesn't guarantee a religion in Deity then why not use piety in the lower difficulties like emperor or king? These difficulty levels will almost guarantee you a religion even if you use tradition or Ethiopia. Saying that Deity doesn't guarantee a religion with piety is like saying piety will not guarantee a victory which really doesn't. If Deity is too difficult for you that you can't even get a religion with piety then don't use Deity and take it easy. You don't need to constantly force yourself to use Deity and pretend you'll get a religion with tradition. The emperor and immortal difficulties could guarantee you a religion more often than Deity at least but it won't guarantee you victory at th Deity difficulty.
You can actually increase your odds of getting a religion in Diety quite simply. Just select the civs you will play against in the setup and exclude Byzantium, Ethiopia, Celts, Egypt, Songhai & Maya. For good measure throw in the Zulus, Huns & Mongols. These guys have basically no interest in building early wonders or in religion so you will have much less competition for a religion. Select Raging Barbs just to slow the AI a bit more.