Interdominos y la mayoría de proveedores no te van a poder proporcionar todo lo que neceistas para poder activar Google Apps.
Como no tienes hosting y para poder usar Google Apps necesitarás crear un nuevo registro CNAME (si no me equivoco) para la verificación. Yo para ello uso
FreeDNS, que te permitirá editar toda la información de la DNS sin ningún tipo de limitaciones, con lo que podrás activar Google Apps y añadir los registros MX.