I have about 300-400 concurrent connection/users on the site at the same time, on average. I DO NOT have SSH access :/
This is your problem.
Shared hosting companies usually limit more than just PHP memory, you could be reaching i/o, and memory limits elsewhere. You could be inside a VM already and reaching that limit, etc. Shared hosting comes cheap but once you start throwing decent traffic at it they generally suspend your account or you start running up against limits.
I'd advise upgrading with that much traffic to something like a VPS, dedicated server or move to cloud based hosting. You're obviously doing something right with the traffic levels so move off quickly :)