According to “Bosun’s Mate” this nautical expression comes from the time of tall wooden ships. The longest seam in such a ship was the one running prow-to-stern, and was called the “devil”. Like every other seam, the “devil” had to be caulked to keep the ship water-tight. To do this, a sailor had to be lowered by ropes, and this sailor was then literally hanging “between the devil and the deep”.
The term “the devil to pay” derives from the same seam, incidentally. As the seam spans the whole hull, it also runs along the keel, and the bilges. To “pay” (seal with pitch) the seam, a sailor had to kneel face-down in bilge-water. It was a much hated job, “paying the devil”.