Yes you can do that. It doesn't matter who you host your DNS with, there are even free providers that will host it for you. At this point whether you need CNAME or A records is dependent on the server addresses the company gives you.
Lets assume your email host provides you a server with the IP of 20.20.20.20 and your webhost provides you with a website address of mysite.somehost.com and not a specific IP.
In your DNS settings you will configure
mail.yourdomain.com with an A record pointing to 20.20.20.20
yourdomain.com and www.yourdomain.com with a CNAME record pointing to mysite.somehost.com
More information: Canonical Name Record (CNAME) showing the usage of CNAME records as aliases for a single IP and for usage with external servers.