Air carrier pilot reported aircraft cooling became uncontrollable after takeoff. The flight crew requested priority handling and performed an air turn back and precautionary landing at departure airport.

Narrative

Ambient temperature in EWR was 95-100 degrees F. We had been operating in an aircraft with no functional APU; thus relying on ground air to cool the cabin while at the gate; and air starts to start engines. This was our 3rd leg in this aircraft on this day. After conducting an air start at the gate; the cabin temperature was 32 Degrees Celsius and the cockpit 36 Degrees Celsius. We taxied out; there was no cooling provided by the packs. We discussed returning to the gate given the long line-up for take-off. After discussing with Ops; they indicated they would contact ATC and expedite our departure. We agreed to wait 5 mins for this resolution or return; worrying that sitting for too long at these temps would be dangerous for passengers and crew.On each previous leg; the aircraft had immediately and significantly cooled upon takeoff. We were expedited and given a back-taxi down Runway 22R to skip the queue. Upon take off; the vents started to pump extremely hot air into the cockpit and cabin. The temperature was steadily rising. We began discussing this issue; and when the temperature reached 43 degrees Celsius (110F) we decided to return to EWR. With temps set to cool to 18 C we had no other means to significantly cools the cabin The trend was alarming; with the temp never decreasing; and continuing to increase rapidly. The air vents became almost too hot to touch.We requested priority handling in order to be given priority for our return and an expedited taxi to the gate and the ability to open the doors and connect ground air. It was clear that extended exposure to these temperatures was a serious safety concern to passengers and crew; and was going to become a very difficult environment to safely perform our duties. The diversion was uneventful and we landed safely and returned to the gate and immediately opened the doors and connected PCA(Pre Conditioned Air).