Надо сделать программу для андроид в будущем может для айфон, на сервере должны храниться данные которые могут менять на андроиде пользователи и то что он изменил должно измениться у всех пользователей. с чего надо начать, хочу сделать сервер на google ingine на python и нужно ли будет использовать GCM
Да можно. Смотрите стартовую документацию по GCM - там расписан порядок взаимодействия вашего сервера с облаком GCM и мобильным приложением.
Требования к серверу изложены здесь - неважно на чем он будет написан, важно что он должен поддерживать или HTTP или XMPP протоколы. В каждом из случаев четко прописаны специальные требования.
Чтобы не заниматься велосипедостроительством я бы посоветовал обратить внимание на готовую серверную инфраструктуру Parse - он поддерживает все то о чем вы написали: хранение, синхронизацию, GCM и проч.