Hey omgmandude,
I will try to be as succinct as I can. Just to be clear, the following information is based on Western musical tradition and not other worldly ideas of music.
When you play a C major chord (as you've described C-nat, E-nat, G-nat) each pitch in our standard scale system (Western tradition, that which involves 12 pitches, spaced by half-step intervals) will sound uniquely different when played against the chord. This is because of how the consonances and dissonances of each pitch in your melody relate to the chord, and either clash (e.g. adding an F#, which creates an augmented 4th) or support it (adding a F-natural, which creates a perfect fourth). It seems you think that you are limited to only playing either a C-nat or E-nat or G-nat in your melody when a C major chord is sounded. However, that is incorrect and only merely objective - you are more than free to do as you wish. Your melody will be based on the dissonances and consonances created as the melodic line, for lack of a better word, "travels" through C major.
Your confusion probably stems from reading/watching general material about chords, melodies, and music theory. It's important to understand that our ears have been trained to hear things in certain ways. If you're brought up in Western Society, your ideas of intonation will be vastly different than those born in other areas, such as India or China - though mixtures of traditions exist everywhere and go back far in the history of music. Use your ears to create your melodies and chord structures. If you enjoy the sound being produced, then nothing should deter you from committing to it, even if it sounds completely alien to others. All of the world's most influential composers (e.g. from the renaissance to the present) expanded music by exploring the boundaries "set" in their respective traditions.
You asked, "all the notes of the melody has to be either C,E, or G". Nothing "has" to be - things must be as you wish. If that resonates well or not with an audience, so be it.
What I am trying to say is that you should explore the boundaries of your melodies (also harmonies, and rhythms). A good exercise to do, if you have a keyboard, would be to play and sustain a C major chord and then take time to play each individual pitch (all 12 of them) and see how your ear reacts to each dissonance and consonance.
I hope I've helped in some way.
Feel free to ask me anything else if you still have questions or concerns about anything I've said.
HISH
