Bueno en parge tienes razon Hounter hay varias empresas mexicanas que tienen los precios algo muy altos, pero ya te puedes encontrar una que otra que de a unos buenos precios, sobre los pagos en deposito bancario o paypal encontraras muchas, ya es solo cuestion de que tu elijas la que mas te agrade y se acomode a tus planes aqui te paso algunos buscadores donde puedes buscar empresas mexicanas de host:
http://www.buscahost.com http://www.buscahosting.com http://hosting.astalaweb.net http://www.hostsearch.com
sobre tu comenario sobre el shell uff va estar dificil que encuentras alguna que lo tenga habilitado ya que muchos no dejamos habilitado el shell por cuestiones de seguridad.