Sometimes I write all the words first (though I never did it that way until I took a six-week songwriting course a couple years ago). I never write the melody first. Often, though, I write both at the same time, or sort of back and forth. I haven't found it necessary to have an instrument at hand to write melodies, but I am heavily dependent on written music. So when I write, I actually write. I keep a pad of manuscript (score) paper on a table next to my bed so I can jot down ideas without getting up.
One drawback to writing without an instrument (for me, that is--people with perfect pitch or who are better at hearing and identifying intervals in their heads don't have this problem): I sometimes slip to the wrong line or space on the staff, which throws off everything beyond that point. Even worse, sometimes I slip back and forth or mis-remember one or more intervals. What happens, though, is the errors frequently lead to an even better melody.
It seems more difficult, to me, to write melody first, as you have to make the words fit within the framework of whatever you've done, whereas it's always possible to craft music to fit whatever you have for words. A lot of times, I'll get my words pretty much done, then read through them while listening to various beat loops and/or chord loops, until I find one or more that "goes with" the words. That usually starts sparking ideas for melodies, too.