A domain is registered with Godaddy. I want to set custom MX records for this domain but Godaddy does not allow me to do this if I don't host the domain there. Since the site is running on my Linode (nameservers point to ns1/ns2.linode.com), I'm wondering if I can set MX records in the Virtualmin or Webmin installations I have on my Linode?

So basically: domain name is in godaddy, nameservers should point to linode and custom MX records should be set. What is the best way to do this taking in to account I can not set them godaddy?

If you have delegated the domain to ns{1,2,3,4,5}.linode.com at your registrar you would set the MX records in the Linode DNS Manager.

Thanks, just made the necessary changes.

and what if domain is on godaddy, we are pointing A record to Linode and also need to send mails using Linode. What MX entries we should do in godaddy?

If you have an A record for example.com pointing to your Linode's IP address, that's all you need. Mail to someone@example.com will be directed toward your Linode. Note that you must not have an MX record for example.com for this to work.