There are several uses of the word no. The UK version of the MacMillan dictionary has this definition
used for saying that there is not even one person or thing
with examples such as
There was no hospital in the town.
We frequently say
I have no idea
So I see
He had no pencil
As being in line with these examples, and as a UK native English speaker, would not have questioned such usage. I must admit now the usage is challenged the phrase does seem a little archaic. However I still believe the formulation is valid. We can see "no" as replacing a count when the count is zero.
He had 5 pencils.
He had 1 pencil.
He had no pencil.
I do wonder whether
He had no pencils
Would be better.
According to this answer "no" is not strictly a count, and may be used with singular or plural nouns.
In the second case we are correcting a previous incorrect statement
He had a pen.
He had a pencil not a pen
we are correcting the subject of had; the subject is not pen it is a pen so we include the full subject we are replacing.