Some considerations:
DNS:
There is potential for people to set up a partial DNS that stores a fraction of the entire set, but with enough of them, the entire range of domain names would be covered. Alternatively, why not create a P2P DNS? Cache a few tens of thousands of DNS records on each machine, keep some semi-centralized main record, but otherwise see if anyone in the local area can resolve it for you first. Ideally, to resist tampering in such a distributed DNS, multiple requests would be made to different sources, but considering how the aerage internet user tends to revisit a few sites often, they would probably cache most of them within a few days and rarely need to look anything up. Periodic checks for changed records would be required.
Security:
Split the packet into multiple ones, in such a way that some of them, but neither one nor all, are required to retrieve the original, so that if a few are lost or read, it can still work, and the contents remain protected. This only works if each takes a different path and it is hard or impossible to identify what packets need to be grouped and how.
The software itself:
You need to share the client/server software *somehow*, and the current internet is certainly the easiest. Due to the initial scarcity of connection points, it would have to be a background sort of thing that allows regular use to proceed uninhibited. Many people would probably be fairly excited at their first connection, but it would probably take months for that to happen, if not years.
Undoubtably, some people would create their own smaller infrastructure, so planning for such possibilities would be important, both "can we trust it?" and how to interact with it seamlessly if it can be adequately trusted.
If such a network started, it would probably be in small islands where one person gets their neighbours into it for easy and fast LAN gaming and file sharing, with an occasional overlap between islands encouraging growth.
IPv4 would be inadequate, and IPv6 is still ISP-oriented, so a distributed IP format would probably be required, especially if it was designed to carry a standard IPv4 or IPv6 packet until it reached the centralized internet, allowing full compatibility for old programs.