Si no puedes usar la función mail() de PHP .. no la uses. Envia el e-mail por sockets (es probable que tu servicio de hosting tenga desactivado esto también .. sobre todo si es "gratuito" como dices usar) directo por SMTP .. Puedes usar la classe:
PHP Mailer
http://phpmailer.sourceforge.net
Ahí podrás indicar un servidor SMTP de tu ISP o el que uses (aunque requiera autentificación .. pues lo permite esta classe).
Si usas mail() cambiando el servidor SMTP que usa PHP por defecto en tu caso .. lo más probable es que no te funcione por qué PHP no "autentifica" con su función mail() y su configuración.
El cambio de servidor SMTP sería por la función genérica:
ini_set()
www.php.net/ini_set
Por ejemplo:
ini_set("SMTP","smtp.isp.tal");
Un saludo,