I would guess someone invented the handshake in prehistoric times and we just have no medium in which a record could exist aside from an undiscovered cave drawing or something like that. Humans seem to naturally touch hands outside of any social influence or cultural history. Babies reach out and people touch their hands. It seems like a pretty intuitive human action. We touch things with our hands, so other hands seems natural as a thing to touch. The shake just seems like a minor variation on that.