The general guidance (not “a rule”) for students is that all singular, countable nouns must be qualified by a determiner or quantifier – the cat, a month, any apple, one car, my ball, that house, etc.
That guidance is not valid for all functions of a noun – in many cases the noun becomes uncountable and is used to describe a particular example of that noun.
In this case, the guidance is:
If the noun is part of a prepositional phrase, we have
When I was in college / He was at home / They sent him to prison / we did it in bed / I saw it on television / By day, he was a policeman; by night he was a burglar / He went to town by bus.
And we have a double expression – {X preposition X} – which creates an adverbial or adjectival phrase.
Arm in arm, they walked along the road. / They were side by side / Year after year, she grew more beautiful.
If a noun is the name of a general institution, we have
He left college/prison/hospital/home. College/prison/hospital/home is where he ended his days.
There are also some expression of the form {X coordination conjunction Y} in which X and Y form a natural pair – They are husband and wife. / Pen and paper to hand, I started the letter.
If a noun is used to designate one from a class of previously mentioned objects, we have
I had to look after a dog, a cat and a parrot. I left them alone for a moment and, when I came back, dog, cat and parrot were chasing each other around the room.
In your case, we have "Year following year, he waited for the ship to return."
Year following year = "Each year that followed the previous year" and the whole clause is adverbial.
As it is adverbial, the noun(s) are uncountable.