Performance of recommender systems (RecSys) relies heavily on the amount of training data available. This poses a chicken-and-egg problem for early-stage products, whose amount of data, in turn, relies on the performance of their RecSys. In this paper, we explore the possibility of zero-shot learning in RecSys, to enable generalization from an old dataset to an entirely new dataset. We develop, to the best of our knowledge, the first deep generative model, dubbed ZEro-Shot Recommenders (ZESRec), that is trained on an old dataset and generalize to a new one where there areneither overlapping users nor overlapping items, a setting that contrasts typical cross-domain RecSys that has either overlapping users or items. We study three pairs of real-world datasets and demonstrate that ZESRec can successfully enable such zero-shot recommendations, opening up new opportunities for resolving the chicken-and-egg problem for data-scarce startups or early-stage products.