Utilizing conversation policies, also called as interaction protocols, is one of the various efforts that have been devoted to the improvement of agent interoperability. The research on conversation policies so far has focused on developing conversation policy models and standard conversation policies. However, in a dynamic agent society where new agents can be introduced and transaction sequences can be changed, there is a need for agents to handle ad-hoc conversation policies. For this reason, this paper suggests a handshaking mechanism for conversation policy agreements that enables agents to exchange and agree to new conversation policies in run-time. A conversation policy model was designed for dynamic exchange and interpretation in the handshaking procedure. The issue of interpreting the conversation policies at run-time was addressed based on the FIPA ACL semantics. By utilizing the handshaking mechanism of this paper, agents can interoperate with each other more flexibly in a dynamically changing environment without being re-implemented for unknown ad-hoc conversation policies. A prototype agent platform was implemented utilizing the conversation policy model and the handshaking mechanism.