I can't remember for sure what options GoDaddy give you (although I thought they gave you full DNS access), but in any case, I think you're getting confused with NS records - these records point to the servers where the 'actual' DNS records are (A, MX, CNAME, TXT etc).
You need to do one of the following:
- Configure the MX on Linode's name servers and get godaddy to point the NS to linode
- Get any IP addresses / hostnames from Linode to set up your DNS
externally, then configure these with GoDaddy (although you mention this is not possible)
- Get any IP addresses / hostnames from Linode to set up your DNS externally, then configure these with hostgator, and get godaddy to point the NS to hostgator
Difficulty/complication increases as you go downwards, in my opinion! Some hosts (not sure about linode) let you configure your DNS records on their name servers, in which case you'll be able to add your MX directly with them and they'll have pre-configured all of the other DNS records for your services with them, which will be ideal.
Hopefully that makes sense.