John Henry is based on a real man, though his story has been embellished with time, and some of the details are uncertain. Most historians, at least in WV, have little doubt that he did exist.

If you look at the Wikipedia page on Tall Tales, http://en.wikipedia.org/wiki/Tall_tale, it even has him marked as being based on a historical indivdual.

Another nice fiction with a similar theme: http://en.wikipedia.org/wiki/Fitzcarraldo