I've used
dnsmadeeasy.com for a while and like the service. It's not
free, but at $15/year (almost $1/mo), it's very cheap and lets you
manage all the DNS settings you mention. There's also some valuable
add-ons for a little extra, like mail backup in case your mail port
goes down, and failovers.
There are some free DNS managers:
FreeDNS and see
http://hostingfu.com/free-dns
I don't use them so can't comment, but google around for reviews.
After you get a DNS service, point the domain name server record at
your domain name registrar to your new DNS servers. Then modify CNAME
like in the Google Apps docs.
Good luck,
Bill