A search of The Concordance of Great Books (url: http://www.concordance.com/ ) gives this reference to Henry IV part 1, act 2 scene 4:

Sirrah, I am sworn brother
|1H4-2-4| ** to a leash of drawers; and can call them all by
|1H4-2-4| ** their christen names, as Tom, Dick, and Francis.
|1H4-2-4| ** They take it already upon their salvation, that
|1H4-2-4| ** though I be but the prince of Wales, yet I am king
|1H4-2-4| ** of courtesy; and tell me flatly I am no proud Jack,
|1H4-2-4| ** like Falstaff, but a Corinthian, a lad of mettle, a
|1H4-2-4| ** good boy, by the Lord, so they call me, and when I
|1H4-2-4| ** am king of England, I shall command all the good
|1H4-2-4| ** lads in Eastcheap.

Since Prince Hal is speaking, I suppose he couldn't really use Tom, Dick or Harry. I do remember reading that versions of the phrase go back even further, but I can't remember my source.

Bingley

Bingley