Concuerdo con mikolopez, la verdad es que en el Arte "todo es posible", pero para que resulte algo bello hay que saberlo acomodar partiendo de algún principio, como ese que mencionas de que para crear una melodía se pueden usar todas las notas de la escala, sin embargo este principio, aunque "cierto", resulta muy simple, habrá notas que encajen mejor que otras, habrá algunas mas adecuadas de acuerdo al género musical o, mas que nada, a la idea que intentes transmitir, y de acuerdo a eso es el trato y uso que debes darles.
Generalizando, un ejemplo para cuestiones prácticas y sin mucha complicación, si ya tienes creada alguna linea melóica puedes darle una "segunda voz" que siga esta misma linea con otras notas, tomando siempre notas que pertenezcan al acorde sobre el cual está escrita la melodía (y no al tono completo) lo cual reduce tus posibilidades pero hace que siempre encaje, este principio limita la creatividad pero pues siempre encajará todo, ejemplo:
Si tienes un compas con CMaj7 y tu linea melódica es sol, do, si do, puedes crear una segunda voz de esa linea usando notas del acorde de CMaj7, como por ejemplo, mi, sol, sol, sol, hay que tratar que la linea melódica secundaria siga a la superior, si la superior sube, la secundaria tambien, y si la superior se mueve a una nota que no pertenezca al acorde en el que estás, repetir en la secundaria alguna nota que sí pertenezca al acorde. Esto es muy usado en lineas melódicas con metales por ejemplo, pero algo más creativo en este caso para mí sería por ejemplo mi, sol, fa#, sol, y no me preguntes de donde saqué el fa# basado en teoría, solo pienso que en mi linea melódica principal el si me resuelve al do y en una linea secundaria puedo remarcar eso resolviendo de fa# a sol, es mas que nada intuición y pues puede sonar bien, dependiendo.
Otro principio muy común (en la música ranchera se usa mucho por ejemplo), es el crear una linea melódica secundaria con intervalos de tercera descendente respecto a la melodía principal, lo cual generará 3as mayores o menores dependiendo, siempre ocupando únicamente notas de la escala (salvo excepciones creativas que se te ocurran). Aca no importa el acorde en el que estés sino el tono general, si estas en Do Mayor y tu melodía es mi fa sol la si do, la segunda linea melódica sería do re mi fa sol la (todas 3as descendentes de la melodía principal), sin embargo si te das cuenta en las últimas notas serían do la principal y la la secundaria, lo cual puede no funcionar muy bien si caes a determinado acorde, como a un Em que no lleva la, entonces podrías modificar la segunda linea melódica con algo como do re mi fa fa# sol, haciendo que en la ultima nota queden do con sol que encajan con el Em, y además acentuando la resolución de si a do en la melodía principal con un fa# - sol en la secundaria.
La verdad es que crear lineas melódicas secundarias (apegadas a la principal pero con otras notas), si que es todo un Arte, creo que no hay reglas absolutas, solo algunos principios básicos pero lo importante es mas que nada ingenio y creatividad para resolver los posibles problemas que puedan generarse por el movimiento de la melodía principal y su relación con la armonía.
