It's possible, but highly impractical to do it with mobile devices.
In Bittorrent, a central coordinating server (a tracker) tells me which other connected clients have the information I'm seeking, and then I download it directly from my peers.
Bittorrent also has a system called a Distributed Hash Table, where cilents work cooperatively to maintain a database similar to the tracker's function, without any central tracker node. I just have to know the address of one participant in the DHT to download it, and discover the other participants. The government could make it very hard to come by this information on the internet, but if I personally knew a participant I could just ask.
There's no reason you couldn't implement a messaging or social networking system the same way.
Mobile devices would be challenging, though. Users would have to be willing to spend their batteries and mobile data allowances serving other people's data to other people. Unlike in the case of a PC tower connected to a cable modem (where Bittorrent usually runs), these resources are scarce.
Worse, the main way we know of to make this kind of system resilient to attackers (blockchain) is to spend a whole lot of electricity and CPU time just to prove that we've done so (this is what "proof of work" means in cryptocurrencies). This is highly impractical with mobile devices.
Apple or Google could remove the app from the App Store or Play Store, and even delete existing installed copies. Cell phone companies could stop passing traffic that looks like it belongs to that app. Particularly in a mobile context, there would still be ways to shut it down.