Are there documents without titles?
Yes, but only in a trivial sense. As noted in the OP, numerous ancient manuscripts are incomplete. A title would be found either in the superscript (the top) or the subscript (the bottom) of the manuscript, or both. There are manuscripts where these portions are missing and, as a result, the portion of the manuscript that survives has no title.
There are other writings without titles--for example, we have surviving shorthand notes, doodlings on wax tablets, and so on--but for actual published documents, I am unaware of any decent argument for the existence past or present of books without titles (I'd be very interested in a counter-example if anyone knows of one). Whether or not the documents bear the correct titles is a different question.
Getting the right title
There are cases where different copies of a document bear different titles--the Epistle to the Hebrews is a classic example.
Other documents have extraordinarily long titles (e.g. do you know the full title of Darwin's "On the Origin of Species"?), and have been shortened in some versions. A number of patristic writers wrote arguments against the heretical views popular in their times--sometimes with exhaustive titles--and they are commonly known as "Against Heresies", rather than wearing out scribes by repeating the full title.
Paul's epistles as an example
The 13 epistles which begin with the word "Paul" are remarkable in this sense--their titles are incredibly uniform.
The letters attributed to Paul are the only letters in the New Testament (and among the very few in all early Christian documents) that are identified by the audience rather than the author.
If you traveled to Thessalonica in the late 50s and asked the local Christian congregation for 1st and 2nd Thessalonians they’d probably be puzzled for a moment, and then take you to visit the graves of the city founders at the local cemetery. If you asked them for the 1st & 2nd letters of Paul they’d know what you were talking about. If the churches called these letters by the name of the author (it would be rather silly if they did not), how do we explain the incredible consistency of the titles referring to the recipients?
My two cents: somebody (we don’t know who but Luke & Timothy are likely suspects) compiled Paul’s papers after his death and distributed them around Rome as a set. This set consisted of 13 letters (not Hebrews), and they were labeled by the church/person to whom they were addressed. (David Trobisch & E. Randolph Richards have written extensively on these matters)
That there is no competing set of titles for these 13 epistles suggests that the titles were never in any serious dispute. (compare, for example, to the debates that have been had about which Federalist Papers were written by whom).
Formally anonymous works
It is fashionable these days to point out that the Gospels are formally anonymous. While this is true, it is likewise true in a trivial sense. Go to your bookshelf and check--almost every book there is formally anonymous in exactly the same way the Gospels are: in almost all cases the author is never identified in the body of the text.
You know who wrote these books because the cover and/or introductory pages provide additional details. The idea of a title page didn't exist in the modern sense in a world that wrote on scrolls. Instead, a tag was attached to the scroll to provide the key bibliographical details. Unfortunately, even where the manuscripts have survived, the tags generally have not.
So the fact that the document may be missing a tag, superscript, or subscript today does not mean it was any more anonymous when it was published than are most of the books on your bookshelf.
Sometimes the title of a document does not identify the author--for example, the Federalist Papers cited above. But when this happens, various views tend to emerge as to who the author was, rather than everyone studying the issue independently coming to the same conclusion.
The surviving manuscript evidence
I'll refer here to intact manuscripts, by which I mean manuscripts with a surviving superscript and/or subscript.
- The number of intact Gospel manuscripts without a title: 0
- The number of Gospel manuscripts attributed to someone other than Matthew, Mark, Luke, or John: 0
- What % of intact Gospel manuscripts attribute the Gospels to the same names listed in modern Bibles: 100%
The original audiences would have known who the author was; the idea that the document did not identify its author is speculative, it is supported by 0 manuscript evidence. But the idea that the recipients didn't know who wrote this document (keep in mind some of these recipients were willing to die for what these document said) is absurd.
For a very deep dive reviewing the evidence on Gospel titles, see the work of Martin Hengel.
The manuscript evidence is 100% consistent in supporting the claim that the Gospels were written by Matthew, Mark, Luke, and John.
Addendum to address a popular counter-argument
Some give great weight to the fact that there are differences in the titles on the gospel manuscripts; it's worth addressing what those differences are (since that part somehow seems to get ignored by those making this argument).
The existing early titles of Gospel manuscripts are variations of two basic ideas:
- "According to Matthew"
- "Gospel according to Matthew"
Far from demonstrating a conspiracy to invent titles after the fact, it shows that the attribution to the author is older than the genre of "Gospel". "Gospel" has not been a genre of literature from eternity past, but rather the terminology appears to have originated sometime around the late first or early second century, and by the late 2nd century it became the preferred, widely-used nomenclature. Early terms for "Gospel" or "Gospels" may have included "memoirs of the apostles", λόγια ("logia"), and/or אִמְרָה ("imra").
The Didache may be the earliest surviving document to make reference to a written Gospel (see Didache chapters 8 & 15). Others have said the origin of the term is even older and is found in 2 Corinthians 8 (see here). The term is definitely known to Justin in the mid-second century, though he often refers to them as memoirs. By the time of Irenaeus (~180) the genre title "Gospel" is clearly well-established and preferred, and at that point it was Irenaeus' focus to delimit the genre (see Against Heresies 3.1).
So whichever Gospel was written first probably wasn't called "a Gospel"; the idea that it should be referred to as such came later, after more, similar documents were written and churches started seeing them as a set that was distinct from other documents.
If the term "Gospel" was not on the original, we should expect to see variation on this point in the manuscripts titles--and we do. If the name of the author did not accompany the original, we should expect to see variation on this point in the manuscript titles--and we do not.
The uniformity of titles naming Matthew, Mark, Luke, and John suggests that this attribution goes all the way back to the originals.