I had a thought a few days ago while I was thinking about conlangs. If a language had a strict verb-final order, it could easily get away without using punctuation to show the end of a sentence.
German somewhat does this. Its sub-clauses are always SOV (simple sentences are normally V2 order). This means that the end of a sub-clause is marked by the verb, which makes center embedding rather easy.
Of course, there are languages that really were written without punctuation in the past. East Asia didn't have punctuation until recently. And Latin, at least early on, didn't even put spaces between words. Of course, the far east has an advantage in that they use logographs heavily (though Korean has largely abandoned their use). Thus they don't need to use spaces to show word boundaries (and yes, I know Japanese has a syllabrary, but word boundaries are still pretty obvious most of the time since logographs have to always appear at the beginning of a word, thus a syllable followed by a logograph always indicates a word boundary). Also, both Japanese and Korean are SOV. Chinese, however, is SVO and configurational. I don't get how they could get away without marking sentence boundaries.
And note, this was all in the ancient past. There's probably a good reason why languages today all have punctuation. They at the very least will indicate the boundary between sentences, if nothing else.