А почему бы тупо не использовать protobuf - http://code.google.com/p/protobuf/
Вроде как он специально под такие случаи создан. Да и пример сервера для питона есть - http://code.google.com/p/protobuf-socket-rpc/ - старенький, правда, но для начала пойдет.

Можно, конечно.
Вообще то все они созданы для сходных целей, и каждого свои особенности.
Буквально сегодня познакомился с MessagePack.

Я часто использую protobuf, выбирая его из-за двух основных преимуществ: хорошего и быстрого сжатия при возможности расширения структуры сообщений с обратной совместимостью для разных версий программ.

В данном случае, считаю, json достаточен.