I think it's fair to call a non-repeating sequence of randomly selected, sufficiently tonal notes, on a familiar scale, in the right frequency range, a melody. So I don't think it's fair to say a melody is inherently non-random. I'd say that there only needs to be a sequence of sounds identifiable as individual notes, with a sufficiently dominant pitch as to sound tonal.