Names in the DNS always appear as "fully qualified domain names" in queries, answers, and name server configurations, specifying the complete path from the root to the leaf. A surprisingly small change would be enough to make query names relative rather than absolute, and this change would have interesting and far-reaching consequences.
The first change (and the key) is to the resolution algorithm. When given a referral, instead of repeating the same question at the replacement name servers, trim off the leading labels of the query name, leaving everything up to and including the leftmost label of the delegation NS records.
Authoritative servers will have to distinguish zones by just their apex label, because that's all that is available in incoming queries. This means that, unlike at present, a nameserver will not be able to serve different zones for example.com and example.net.
This modification means that names now trace paths in a graph, rather than being hierarchial addresses. The graph can be cyclic, for example, if zone A has a delegation to zone B which in turn has a delegation back to A, then names can have an arbitrarily long sequence of A.B.A.B.A cycles round the loop.
How does resolution start in this setting, when there is no root? You (or your ISP) would configure your recursive name server with one or more well-known starting zones, which would function rather like top-level domains.
The key difference between this arrangement and the root zone is that it allows diversity and openness. The decision about which zones are starting points for resolution is dispersed to name server vendors and operators (not concentrated in ICANN and the US DOC) and they need not all choose the same set. They can include extra starting zones that are popular with their users, or omit ones that they disapprove of.
Unlike the hierarchial DNS, you can still resolve names in a zone even if it isn't in your starting set. It will be normal for zones to have delegations from multiple parents, ensuring that everyone can reach a name by relying on redundant links instead of global consistency. So the berlin zone might be generally available as a starting point / TLD in Germany, but if you are in Britain you might have to refer to it as berlin.de.
Instead of a political beauty contest, to establish a new TLD you would probably start by obtaining the same label as a subdomain of many existing TLDs, to establish a brand and presence in your target markets. Then as your sales and marketing efforts make your zone more popylar you can negotiate with ISPs and resolver vendors to promote your zone to a TLD instead. I expect this will force DNS registry business models to be more realistic.
Users may be able to augment their ISP's choice of TLDs by configuring extra search paths in their stub resolvers. However this is likely to lead to exciting RFC 1535 ambiguity problems.
In some respects the relationship between vendors and rootless TLDs is a bit like the situation for X.509 certification authorities. ISPs will have to judge whether DNS registries are operating competently and ethically, instead of relying on ICANN to enforce their regulations.
Trust anchor management cannot rely on policies decided by a central authority, and it will need to cope with a greater failure rate due to the much larger and more diverse population of resolution starting points. Perhaps RFC 5011 automated DNSSEC trust anchor management would be sufficient. Alternatively it might be possible to make use of a zone's redundant delegations as witnesses to changes of key along the lines of a proposal I wrote up last year.
These thoughts are partly inspired by the Unmanaged Internet Architecture's user-relative personal names. And bang paths (in the opposite order) were used to refer to machines in the UUCP network. Some other background is Zooko's Triangle and Clay Shirky's essay on domain names. The PetName system described by Mark Miller is also interesting, and similar in some ways to UIA names.
The rootless DNS doesn't quite reach all the corners of Zooko's triangle. The names are as human-meaningful as a crowded namespace can allow. Names are only global to the extent that network effects promote zones as popular TLDs worldwide - but you can work around this by providing alternate names. Names are secure to the extent that you trust the intermediaries described by the path - and if that doesn't satisfy you, you can promote important names to be trust anchors in your setup.