It could be done without a big lock by splitting into three steps:
1) Push an upgrade that changes the types and adds the conversion functions. The valid type is the union of the old type and the new type. Wait until all nodes complete the upgrade.
2) Push an upgrade that instructs the nodes to convert their data and start using the new types by default. Wait until all nodes complete the upgrade.
3) Push an upgrade that removes the old types and conversion functions.
The problem is whether the function can or cannot handle the content of the new message and that's completely orthogonal
You could still use Erlang's crashing and supervisor technique, but you would have the additional benefit of using static typing across a distributed system (where each node may or may not have received the upgrade yet).