This linkhas this to say:

BETWEEN A ROCK AND A HARD PLACE -- From "Random House Dictionary of Popular Proverbs and Sayings" (1996) by Gregory Y. Titelman(Random House, New York, 1996): "Between a rock and a hard place. Forced to choose between two unpleasant options. The expression originated in the early twentieth century in the United States. It usually follows 'to be caught'…" The "Encyclopedia of Word and Phrase Origins" by Robert Hendrickson (Fact on File, New York, 1997) says "the expression was probably born in Arizona during a financial panic early in this century…"

I hope my cut and paste works.

A follow up post to that thread suggests that the Russians couldn't win a war in Afghanistan because they were between Iraq and a hard place.

Bardford