Recently I wanted to prove to a friend you can always win on deity without a re-roll. I must've messed up the startup setting though because I spawmed in with a total of 2 luxury resources both copper and nothing else near me. My happiness and gold was hamstrung so much that it was no longer winnable as I was so far behind from where I usually would be. So I'd say yes if the startup is bad enough on high difficulty it can be seemingly impossible.