Words and melody first, methinks. Musically, that's the line that you hang the chords on.
I have a friend who is a fairly accomplished poet. Some published work, many poetry readings. His theory, based on considerable knowledge and research, is that the words are of primary importance. Not surprising, coming from a poet. But he has a point. The Story. After all, ballads are narratives — and songs, even though they might not tell a story straight-out, usually imply a story. My poet friend maintains that way back in the mists of antiquity, history was cast in the form of long narrative poems which were sometimes chanted — Homer's Iliad, and many epics and sagas (e.g., Beowulf). Rhyme, meter or rhythm, and melody functioned as mnemonic devices. An accompanying instrument, such as a lyre or harp, acted to enhance the melody and punctuate or accent certain parts of the narrative. Interesting, I thought. Bards were the historians, and vice versa.
Thought experiment: consider all the songs that you have memorized and ask yourself how well you could recite them. Not sing them, recite them. No melody, no accompaniment, no music. How do you think you would do? I know that I wouldn't do all that well.
I usually start out learning the words and melody together, getting to the point where I can sing the song without accompaniment (I also pay particular attention to enunciating the words clearly). By then, my voice has decided what key I'm going to do it in. My voice is fairly deep, so I can't sing most songs in the same keys they're in on a CD or in a songbook (except for Gordon Bok. Great stuff!). Being able to sing your songs without accompaniment has the advantage that your songs are always with you, and don't depend on where your guitar, banjo, autoharp, or whatever happens to be.
Once I have the song learned, I pick up the guitar and figure out an accompaniment. Simplest possible first. How few chords can I get away with and still have it sound good? Once I have the basic chords, I begin to experiment, substituting chords ("Okay, the melody note here is C, so which chord sounds best, C or F?"), seeing if relative minor (or major) chords fit ("How about an Am there?"), sometimes trying some really odd-ball chords from other keys just to see ("Cm? Nope. Ab? Ouch! Didn't think so."). As long as you're by yourself, if you hit a real clanker, nobody will know but you. And sometimes you do find the magical chord. Once I have the chords down, at least tentatively, I play around with right-hand patterns, bass runs, countermelodies and such. Some accompaniments have to stay fairly simple, otherwise they detract from the song. Other songs can support some pretty flashy instrumental work. I like to think of it as being like a frame around a painting. A simple molding is all you need around some paintings; an ornate, rococo frame would overwhelm it. But an ornate frame might look pretty good around some other painting. You have to use your own judgment.
Words and melody. Then the chords. At least that's the way I do it.