A321 flight crew reported bleed air initially inoperative after take-off leading to uneventful diversion.

Narrative

Originally scheduled as ZZZZ-ZZZ. Aircraft arrived ZZZZ with APU inop. Performance data required a BLEED AIR-OFF take-off for heavy weight. Following take-off; we attempted to turn the bleed air and packs back on and received AIR - BLEED 1 + 2 FAULT" ECAM. With no bleed air available; aircraft would not pressurize or cool the cabin. We leveled off below 10000 ft. and turned back toward ZZZZ while attempting the QRH reset procedure. Aircraft was 25000 lbs. overweight for landing so we held at 3000 ft. to burn gas and shorten our landing distance to a safe distance. After approx. 20 minutes of holding; I attempted the QRH reset procedure 1 final time and all faults cleared and the aircraft began to pressurize/cool the cabin.Aircraft was now operating normally and still 20000 lbs. over weight for a normal landing in ZZZZ (would have required another 2-3 hours of holding to reach normal landing weight). We no longer had enough fuel to reach our original destination so; with dispatch and maintenance concurrence; we elected to divert to ZZZ1. Flight to and arrival into ZZZ1 was normal.The aircraft APU failed as the previous crew was taxiing in to parking in ZZZZ. Had the APU been operating normally; we would have left it running and supplying bleed air to both the pressurization system and the cooling packs throughout the take-off. This situation occurred because; with the high ambient humidity and our using the engine bleeds normally on the ground to cool the aircraft cabin; the bleed valves froze closed when we turned them off for take-off. After approximately 20 minutes of holding with no cooling air; the valves thawed and operated normally. Suggestions: Had the airline given us a Aircraft Y for such a long flight with such a high fuel load; this problem never would have occurred. The Aircraft Y has stronger engines and much better take-off performance and would have alleviated any need for a BLEEDS OFF take off; thus the valves would have remained ON and never would have frozen closed."