Honestly i have no idea how is it possible... I find founding religion absolutely doable on Deity for any religion-oriented civ. And i think you have like 40-50% chance to found for non-religious civ. I'm pretty sure that i can found in every game for every civ on Emperori gave up on trying to found a religion on the exact mentioned settings after loing the race to the last prophet by just one freaking turn three times in a row as brazil, inca and spain.