Sim, você pode fazer isso. Não importa com quem você hospeda seu DNS, existem até provedores gratuitos que o hospedarão para você. Neste ponto, se você precisa de registros CNAME ou A, depende dos endereços de servidor que a empresa lhe fornece.
Vamos supor que o seu host de e-mail forneça um servidor com o IP de 20.20.20.20 e o seu webhost forneça um endereço de website de mysite.somehost.com e não um IP específico.
Nas suas configurações de DNS, você irá configurar
mail.yourdomain.com com um registro A apontando para 20.20.20.20
yourdomain.com e www.yourdomain.com com um registro CNAME apontando para mysite.somehost.com
Mais informações: Registro de nome canônico (CNAME) o uso de registros CNAME como aliases para um único IP e para uso com servidores externos.