[Ar-Pharazon]

The Heathen kings are in referrence to the beginnings of men in the first age. When men came to be the only beings they were in contact with were the dark elves and minions of Morgoth. Times were tough and they were tormented by Morgoth, where they developed their fear of the "gift of death". Many humans became evil and aligned themselves with Morgoth, but not all.

In the Silmarillion many groups of humans flee over the mountain ranges dividing the east and west and encounter the Noldor and the grey elves. They enter into their service and ally themselves with them in the war against Morgoth, they become known as the Edain.

After the war of Wrath and the fall of Morgoth, these Edain are given Numenor and are then known as the Dunedain. During the reign of Numenor they develop the ability to keep the flesh from degrading after death and the dead are then entombed rather then burned. The armies of Numenor then returns to middle earth and conquer many of the Heathen Kingdoms of men which were the descendants of the men that did not become the Edain and are loyal to Sauron.

Their is not much else really said about the Heathen Kings except that the people of middle earth viewed the people of Numenor as godlike and lords of men. So what Denethor is referring to is the time before Numenor was at its apex and it seems implied that man burned their dead

~Ar