Si no te permiten usar la función mail(), entonces verde que puedas abrir conexiones externas (y mucho menos con Gmail, pues éste requiere que la conexión que abras sea segura, por lo que tu hosting debe poder abrir usando protocolos SSL/TLS). Me sumo a lo que los demás ya te dijeron, recomienda a tu cliente que cambie de hosting.
De veras es un hosting pago? Sin conexiones externas, es poco probable que exista alguna manera de enviar mails.
P.D. Prueba usando el método SendMail de PHPMailer.
