It would seem that by the mid-18th Century, the act of keel-hauling was considered (by the British public, at least) to be a Dutch punishment. A contemporary dictionary gives the following definition:
Keel-Hauling, a punishment inflicted for various offences in the Dutch Navy. It is performed by plunging the delinquent repeatedly under the ship's bottom on one side, and hoisting him up on the other, after having passed under the keel. The blocks, or pullies, by which is is suspended, are fastened to the opposite extremities of the main-yard, and a weight of lead or iron is hung upon his legs to sink him to a competent depth. By this apparatus he is drawn close up to the yard-arm, and thence let fall suddenly into the sea, where, passing under the ship's bottom, he is hoisted up on the opposite side of the vessel. As this extraordinary sentence is executed the a serenity of temper peculiar to the Dutch, the culprit is allowed sufficient intervals to recover the sense of pain, of which indeed he is frequently deprived during the operation. In truth, a temporary insensibility to his sufferings ought by no means to be construed into a disrespect of his judges, when we consider that this punishment is supposed to have peculiar propriety in the depth of winter, whilst the flakes of ice are floating on the stream; and that it is continued till the culprit is almost suffocated for want of air, benumbed with the cold of water, or stunned with the blows his head received by striking the ship's bottom.
An Universal Dictionary of the Marine, W. Falconer (1784)
Interestingly, this seems to suggest that the act was (a) repeated more than once for a given punishment and (b) was not directly, or intentionally, fatal.
A footnote in "The Life and Works of Sir Henry Mainwaring" (from a work by Boteler) suggests that keel-hauling might have evolved from the punishment of ducking:
Ducking 'at the main yard arm is, when a malefactor by having a rope fastened under his arms and about his middle, and under his breech, is thus hoised up to the end of the yard ; from whence he is again violently let fall into the sea, sometimes twice, sometimes three several times one after another ; and if the offence be very foul, he is also drawn under the very
keel of the ship, and whilst he is under the water a great gun is given fire right over his head.'
Dialogical Discourse of Marine affairs, Nathaniel Boteler (1685)