Machines do figure out the protocol on the fly by asking each other; see the Accept and Upgrade headers in HTTP, for example. Of course, HTTP is itself a protocol, because you can't "ask each other", or do any kind of communication at all, without a common protocol to start with.

As for making protocols on the fly, that makes roughly as much sense as two people inventing their own language to talk to each other.