Conventional cloud storage services offer relatively good reliability and performance in a cost-effective manner. However, they are typically structured in a centralized and highly controlled fashion. In more dynamic storage scenarios, these centralized approaches are unfeasible and developing decentralized storage approaches becomes critical. The novelty of this paper is the introduction of the highly dynamic distributed mobile cloud, which uses free resources on user devices to move storage to the edges of the network. At the core of our approach, lies the use of random linear network coding to provide an effective and flexible erasure correcting code. This paper identifies and answers key questions regarding the feasibility of such a system. We show that the mobile cloud has sufficient network resources to adapt to changes in node numbers and also study the redundancy level needed to maintain data availability. We have found that as little as 75% redundancy is enough to offer 99.28% availability for the examined period and essentially 100% availability is achieved when using 50% redundancy along with high-availability nodes. We have leveraged traces from a popular P2P mobile application to simulate the processes governing user behavior to show feasibility of mobile storage clouds in real scenarios.