Похоже, JSON может соответствовать всем требованиям. Это просто, и находится в стандартной библиотеке Python .
Возможно, он не слишком рад по поводу кортежей:
>>> import json
>>> a = ((1,2),(11,22,),(111,222))
>>> print a
((1, 2), (11, 22), (111, 222))
>>> message = json.dumps(a)
>>> message
'[[1, 2], [11, 22], [111, 222]]'
>>> b = json.loads(message)
>>> b
[[1, 2], [11, 22], [111, 222]]
Решать вам, является ли это проблемой или нет.