What is the origin of the phrase “guts for garters”?

More likely that the phrase actually refers to shirt garters (worn around the bicep to hold too long sleeves so they just touch the wrist) which were a common men's accessory until quite recently (my Grandfather, wore them) - not sock or stocking garters (which aren't/weren't that common)

The American pop artist S. Clay Wilson drew a cartoon for Zap Comix years ago depicting a bloody shipboard battle between pirates. One bloodthirsty savage growls, "I'm gonna use somebody's guts for a neck-tie."

With regard to the eighteenth-century origins that Eric Partridge claimed for "guts for garters," as noted in user66974's answer, the antecedents of the phrase appear to be considerably older than that. A search of the Early English Books Online database turns up ten approximate matches involving the use of guts as garters from the period 1590–1686.

From Robert Greene, The Scottish Historie of Iames the Fourth, Slaine at Flodden Entermixed with a Pleasant Comedie, Presented by Oboram King of Fayeries (1590/1598):

Purueyer. Sirrha come open me the stable, / And let mee haue the horses: / And fellow, for all your French bragges I will doo my dutie.

Andrew. Ile make garters of thy guttes, / Thou villaine if thou enter this office.

Greene died in 1592 so the instance cannot be later than that year; the circa 1590 date for James the Fourth comes from an online reference; another source dates the play to "1588–1592."

From A Pleasant Conceited Comedie, Called, A Knacke to Know an Honest Man (1596):

Marchetto. Sirra, tel thy mistresse Fortunio is at hand to speake with her.

Gnatto. [within.] Soft sir, keepe out I say, least I make garters of your guttes, foote balles of your faces, ho let forth the dogges there.

From Samuel Rowlands, "The Lettin[g] of Humours Blood in the Head-Vaine with a New Morissco, Daunced by Seauen Satyres, vpon the Bottome of Diognes Tubbe" (1600):

If any fall together by the eares, / To field cries he; why? zownes (to field) he sweares / Shew your selues men: hey, slash it out with blowes / Let won make tothers guts garter his hose, / Make Steele and Iron vmpiers to the Fray, / You shall haue me goe with, to see faire play: / Let mee alone, for I will haue a care / To see that one do kill the tother faire.

From Ben Jonson, The Fountaine of Selfe-Loue. Or Cynthias Reuels (1601):

Hedon. Heart of my father, what a strange alteration has halfe a yeeres haunting of Ordinaries wrought in this fellow? that came with a Tuff-taffata Ierkin to Towne but th'other day, and now hee is turn'd Hercules, hee wants but a Club.

Anaides. Sir, I will garter my hose with your guttes ; and that shall be all.

From Samuel Rowlands (again), The Knaue of Clubbs (1609):

Now euery man must to his purse againe, / In Vintners debt, and Fidlers they remaine, / Some sweare, some swagger, others laugh thereat, / Wishing the reckning would make thin-gut fat: / A pox vpon this Poet one did curse, / He hath not left a penny in my purse: / Fiue shillings not a farthing more I had, / And thus be-guld, doth make me almost mad, / With all my heart I'le spend a crowne, or twaine, / To meete the rascall in my dish againe: / I would bestab his skin, like dublet cuts, / And garter vp his stockings with his guts. / Then downe the staires the villain should be tost / Like •• a footeball in a winters frost.

From Thomas Heywood, The Foure Prentises of London, With the Conquest of Ierusalem (1615):

Evstace. He strikes his owne soule downe to Erebus, / That lifts a sword that shall but touch his haire.

Irishman. And by S. Patrick I'le make him Garter his hose with his guts, that strikes any stroke here.

From John Gaule, Distractions, or The Holy Madnesse Feruently (Not Furiously) Inraged Against Euill Men (1629):

Take heed of him; hee hath drawne his blade, and vowes, not to put it vp, till he be reuenged: His Life (he sweares) shall answer for the Wrong. Oh how hee'le hacke him, and hew him, the next hee meets him. Doe you heare him? Hee'le cleaue his Coxcombe, bumbaste his hide, rattle his bones, split his heart, let out his puddings about his heeles, and garter him in his guts. His bloud is vp; and will not settle, but in bloud. Outragious and bloudy villaine!

From A New Booke of Mistakes. Or, Bulls with Tales, and Buls Without Tales But No Lyes by Any Meanes (1637):

Now for these here related, they claime no Kindred from the blacke Bull in Bishopsgate street, who is still l•o•ing towards Shorditch, to see if he can spy the Carriers comming up from Cambridge; nor from the branded Bull at St. Albons, who would tell all Travellers, if hee could speake, There you may have Horse-meate, and Mans meate for your Money; nor from the White Bull at the Beare-garden, who tosseth up Dogges like Tennisballs, and catching them againe upon his Hornes, makes them to garter their Legges with their owne Guts; nor from the Red Bull in Saint Johns streete, who for the present (alack the while) is not suffred to carrie the Flagge in the mainetop; neither have they any Alliance either to Cow-crosse, or Cow-lane: But these are such as have Teeth, and bite not; and Hornes, yet butt not.

From Robert Baron, Erotopaignion, or, The Cyprian Academy (1647):

It sufficeth not that thou hast subdued yonder Petitoes of Mars, and captived their Lady, fortune will not sell her at so under a rate, it remaineth that you vanquish me also before you injoy her, the wager of our contention, whose mercy i'le constraine you to abide, and in whose defence my sword (blushing at thy impieties) shall strike thy soule to Erebus, and compell thee to garter thy hose with thy gutts.

And from George Stuart, A Joco-Serious Discourse in Two Dialogues Between a Northumberland-Gentleman and His Tenant, a Scotchman, Both Old Cavaliers (1686):

Tenant. ... "Let them take warning, I'll take course, / If they'll not dance they shall do worse. / We'll flail them into better Manners, / And sell their skins to Godly Tanners; / Or if we stop them well wi' Straw, / They'll fley the Tory's all awaw. / I guess they've heard what this days Vote is, / We'll (y) paik their Hides, let them take notice. / They may expect, but find nae Quarters, / We'll make their very Guts their Garters: / They canno' say but I ha' warn'd 'em; / Yet still they parted and nae harm done.

---

Conclusion

It thus appears that the expression "guts for garters" owes its origin to multiple instances in the late sixteenth and early seventeenth centuries of the notion of "making garters of [one's] guts." Because Robert Greene, the anonymous author of A Knacke to Knowe an Honest Man, Samuel Rowlands, and Ben Jonson all used similar expressions in texts written within about ten years of one another starting around 1590, it seems plausible that all of these authors were simply using an expression that was already in contemporaneous nonliterary use. However, credit for the first written instance of the expression—to judge from the EEBO results I turned up—goes to Greene.