I start with melody, and since I sing, and good lyric. Then I find the right chords and feel, both of which are usually suggested by the melody and lyric.
I try to perform the song live at gigs, or at least record it, to get an idea of how it sounds. Live performance is the best option imo to see if it works.
Whether or not it's "fresh and still listenable" are tough to judge. I try to write songs I like. Maybe listenable to some, not to others. It seems that many of the jazz boards frown upon vocals in jazz and vocal jazz (and song components like lyrics) gets ignored and often looked over or just dismissed.
Even though jazz is notoriously difficult to define, I prefer the vocal side of it.
