Should nonchord tones be avoided since they are "dissonant"?
The WHOLE point in melodies is to produce tension and release. How do you expect to produce any tension when the notes are all consonant - as in they all fit nicely? By using notes that ARE dissonant, the tension is made. The listener squirms a little, until the dissonance is resolved with consonance.
Making everything consonant, where's the tension? 'Nuff said.
No. Dissonance is good. It allows us to resolve to consonance. Or not. An unresolved dissonance can sound interesting.
'Theory' describes what you've done. It doesn't tell you WHAT to do. (Well, it can make some pretty strong suggestions! But you carry on writing what you think sounds good. Theory will be able to cope with it.)
Any tone (chromatic, also) can be used in a melody. Dissonant notes do have a different effect if accented than if unaccented. For example, against a C chord, a melody proceeding C-D-E with the C and D accented makes for a smooth melodic movement from E to C. If one played C-D-E with the D accented makes for a more angular sound. Neither of these is wrong; you choose which sounds better. An accented dissonance calls attention to itself; one often uses these at cadence points (or any other point that needs the listener to pay a bit more attention to.)
The proposition in your question title rules out the majority music that has harmonic accompaniment. If a melody cannot have non-chord notes, it is restricted to arpeggios of the chord. If you sing "mary had a little lamb" in C while playing that chord, that has D in it which is not in the chord: EDCDEEE.
In the Blues, you often hear combinations like a solo in a minor pentatonic scale, with a tritone, and micro-tonal note bends, over a V7 chord at the same root. Half the notes are not in the chord. The root, fifth and minor seventh degrees of the scale are in the chord, but the minor third and fourth are not, and neither is the tritone nor any additional microtonal pitches.