How can we sign a contract digitally between two parties? I'm trying to sign a contract with another party, without using handwritten signatures. 

I've just read through Applied Cryptography, but there doesn't seem to be a protocol that can solve this problem. Digital signatures simply don't work. Even if the other party signs the contract with his private key and I can verify it using his public key taken from a Certificate Authority, he can claim that he had lost his private key, and an imposer had signed the document.

In fact, he can shamelessly broadcast his own private key anonymously over the internet moments before he signed the document with me, thus securing his "proof" that everyone has his private key at a time before the document was signed. Besides this, there are many other reasons why digital signatures cannot achieve non-repudiation, as elaborated by D.W. in another post.

What alternatives do we have?

How can we make digital signing work?
No.  Cryptography alone cannot solve this problem.

Solving this problem requires a combination of technical (e.g., cryptography, systems security) and non-technical (e.g., legal, regulatory, contractual) solutions.  Even the technical part is not solely a cryptography question; it as much about systems security.