The Port Authority website contradicts itself here where it appears to indicate there is still baggage storage at terminal 4 as well:
http://www.panynj.gov/airports/jfk-s...-services.html
For terminal 4 there is a line item:
Hotel Reservations/Baggage Storage/Lost & Found Pre-Security Arrivals Hall
No phone number is given.