Now, I've heard there was a secret chord
That David played, and it pleased the Lord
But you don't really care for music, do you?
It goes like this, the fourth, the fifth
The minor fall, the major lift
The baffled king composing hallelujah
Your faith was strong but you needed proof
You saw her bathing on the roof
Her beauty and the moonlight overthrew ya
She tied you to a kitchen chair
She broke your throne, and she cut your hair
And from your lips she drew the hallelujah
I'd like to point out the second verse is all about failures. "Your faith was strong but you needed proof" probably references Gideon, who had God perform miracles to prove that he was really the one God wanted. "You saw her bathing on the roof / Her beauty and the moonlight overthrew ya" references, of course, David and Bathsheba - David saw her, killed Bathsheba's husband, and took her as wife. "She tied you to a kitchen chair / She broke your throne and she cut your hair" probably all references the story of Samson and Delilah - Samson wanted Delilah even though he'd been warned not to be with her, and then she tricked him and cut his hair, removing his God given power. His actions eventually caused his death.
A lot of the Old Testament is about God choosing a hero or rescuer, and the hero, rescuer, Israel, or all of the above, failing, and God forgives again. Just look, for example, at the book of Judges (though really almost any Old Testament book would do).
David is baffled for several reasons, then:
- He's in awe of the grandeur of God - this is a theme throughout the Old Testament as well, so this isn't really a reference to the next verse. ("O Lord, our Lord, how majestic is your name in all the earth!" - Psalm 8:9 is just one example of one of a verse written by David in awe of or praising God.)
- He's in awe that in spite of his failures, God is still listening to him, and being pleased by his work. (There's references to this in the Psalms, as well.) I mean - he was God's chosen, but then he killed someone and took their wife. God was displeased with him, but forgave him and loved him still. That's outright baffling, that kind of forgiveness. He's also, in that sense, thanking God with his hallelujah - a thank you for being forgiven.
To explain #2 a little more - David was incredibly ashamed after he committed adultery with Bathsheba. In Psalm 51, listed in the NIV as "A psalm of David. When the prophet Nathan came to him after David had committed adultery with Bathsheba" David says
Have mercy on me, O God (51:1)
Do not cast me from your presence (51:11)
In an earlier Psalm that David wrote in another time of trouble and his own sin, he writes
O Lord, do not rebuke me in your anger
or discipline me in your wrath (38:1)
My guilt has overwhelmed me
like a burden too heavy to bear (38:4)
Note that the phrase "overwhelmed me" here reflects the phrase "overthrew ya" in Cohen's song. Psalm 39 continues his expression of pain and guilt, and then in Psalm 40
[...] the Lord
turned to me and heard my cry.
He lifted me out of the slimy pit,
out of the mud and mire;
he [sic] set my feet on a rock
and gave me a firm place to stand.
He put a new song in my mouth (40:1 - 3)
In 2nd Samuel, it says
Then David said to Nathan [God's prophet], "I have sinned against the Lord." Nathan replied, "The Lord has taken away your sin. You are not going to die." (2 Samuel 12:13)
Normally, the penalty for adultery and murder was death, but God forgave him and removed the death penalty for him, though David was still punished. Interestingly, after David was punished (his child by Bathsheba died), he immediately washed and "went into the house of the Lord and worshiped" (2 Samuel 12:20), which is reminiscent of Cohen's line "And from your lips she drew the hallelujah" - David's sin in a way caused him to praise God.
Throughout the Psalms, David's poetry alternates between begging for forgiveness, thanking God for the forgiveness, and praising God. Throughout the Psalms, David also asks God a lot of questions - showing he's quite often baffled by God's actions - but the best one explaining this verse of Hallelujah is
What is man that You are mindful of him? (8:4)
David is literally in awe and astonishment that God pays any attention to man, forgives man, has given man ownership of anything (later in the Psalm David says "You [...] crowned [man] with glory and honor"). No wonder David is "the baffled king" in Cohen's verse. Later in the same Psalm, David says "O Lord, our Lord, how majestic is your name in all the earth!" (Psalm 8:9) - he is literally a "baffled king composing hallelujah" - he goes right from being baffled to praising God. This is exactly Cohen's line.
The term "baffled" may also refer to Cohen's own creative process:
Its composition famously reduced Cohen to sitting in his underwear on the carpeted floor of his room at the Royalton Hotel in New York, filling notebooks, banging his head against the floor. - The Guardian
Cohen may have pictured David similarly "banging his head" and then coming up with the "secret chord [that] pleased the Lord" and being a bit baffled on what happened inbetween.
As for this being a nonlinear story, I think it was kind of meant to be. Cohen wrote over 80 verses of the course of an impressively long period of time (I think around a year). The various covers of the song pick and choose verses, and mix them up, to represent their own subtheme (love, forgiveness, etc). As Wikipedia says:
Cohen's lyrical poetry and his view that "many different hallelujahs exist" is reflected in wide-ranging covers with very different intents or tones, allowing the song to be "melancholic, fragile, uplifting [or] joyous" depending on the performer: The Welsh singer-songwriter John Cale, the first person to record a cover version of the song (in 1991), promoted a message of "soberness and sincerity" in contrast to Cohen's dispassionate tone; the cover by Jeff Buckley, an American singer-songwriter, is more sorrowful and was described by Buckley as "a hallelujah to the orgasm"; Crowe interpreted the song as a "very sexual" composition that discussed relationships; Wainwright offered a "purifying and almost liturgical" interpretation; and Guy Garvey of the British band Elbow made the hallelujah a "stately creature" and incorporated his religious interpretation of the song into his band's recordings.
All quotes from the Bible in this answer are from the NIV Study Bible from 1995, edited primarily by Kenneth Barker, though with help from Burdick, Stek, Wessel, and Youngblood.