Здравствуйте, Tom, Вы писали:

Tom>Как вы думаете, реально ли, с юридической стороны, сделать сервис хранения и работы с пользовательскими данными.

Конечно реально.

Tom>Как вообще подойти к разработке EULA для подобных сервисов.

Как всегда — тырить у аналогичных сервисов. Например вам подойдут сервисы бекапа контактов с телефона, да и любого другого бекапа.
Вот например кратко: https://www.everdroid.com/web/#termsofservice
Или длинно: http://www.idrive.com/idrive-lite/contacts-backup-terms.htm