My thoughts are:
There's an infinite number of possible melodies because:
There are 12 notes in standard tuning, 24 in Quarter-Tone tuning, some cultures use a more pentatonic tuning, but no matter how many notes there are, there is a finite number of arrangements sans repetitions. However repetitions are extremely common and virtually everywhere, both rearticulations and back and forth motions, Examples of rearticulation: Anything by Beethoven pretty much, Impromptu in Ab Op. 142 No.2 Schubert(both bass and treble rearticulations here), and hundreds more, Examples of back and forth motion: Virtually every piece written between the Renaissance and Stravinsky and even a lot beyond that
There's more to melody than just note arranging too, even in the least structured melodies, rhythm plays a big role. And there are a lot more note values than most people realize. From Renaissance to Romantic you have these basic note values: 256th, 128th, 64th(I've seen notes that short in Bach's Toccata and Fugue in D minor for instance, right at the beginning of the Tocatta), 32nd, 16th, 8th, quarter, half, whole, double whole, and Longa(4 whole notes) + most of the possible dotted forms + even more of the triplet forms and so on.
You can always do an octave transformation of any melody + Inversion, Retrograde, Retrograde Inversion, Augmentation, Diminution, and Stretto
And lastly, all melodies have structure to some degree. Whether that's just tension and release points or whether it's whole phrase repetitions, there is structure. Whether all of the melody can be boiled down to 1-3 motifs and their transformations or not, there is structure. But structure doesn't limit us to a finite number of melodies
Even in pieces that are literally just repeated chords(Chopin's C minor Prelude for instance) there is a melody and there always will be. Moonlight Sonata First Movement is another piece that I've heard of being referred to as no melody because there is so much harmony and what melody there is fits right in. So? The sheer abundance of harmony(chords, arpeggios, Alberti Bass, whatever) does not preclude the presence of melody. And both the Moonlight Sonata First Movement and the Chopin C minor Prelude show that a piece made entirely out of harmony still has a melody within the chords. Chordal melody in general is quite common, especially in the Classical and Romantic eras.
I generally just improvise the melody on the spot. If there is a countermelody, I do the same for it and then listen. They generally turn out very good, complementing each other, when there are only 2 melodic lines anyway, with 3 it gets exponentially harder to get both independence of lines AND dissonance that isn't out of place, especially when the melodic lines tend to be within an octave of each other, which mine do with 3 lines and even more with 4 lines, have the average max distance of 1 octave between a pair of inner voices or a pair of an outer and inner voice, usually much closer to a third for the inner voice pair.