This is unclear, but we can make some presumptions as to who it may be.
It is my opinion that this was about the Kings who fell under Sauron's control in the second age. Although no confirmation is given in the Legendarium which kings burnt themselves alive, we know some did.
Besides the above quote, we have the following from Gandalf:
Authority is not given to you, Steward of Gondor, to order the hour of your death,' answered Gandalf. 'And only the heathen kings, under the domination of the Dark Power, did thus, slaying themselves in pride and despair, murdering their kin to ease their own death.
Return of the King: Book 5 - Chapter 7
Although this doesn't confirm that it was Sauron it suggests it was either Sauron or Morgoth. This occurs a few chapters after Denethor's comment, and although the Gandalf wasn't there when Denethor said it, he says something very similar. This seems to suggest that this piece of history is something known well by at least the most learned in Middle-earth. Which leads to my assumption that it was the Kings of Numenor. As their history is one of the most detailed given.
However, in the History of Middle-earth there is another mention of the word heathen with regards to the Kings of Numenor. However this time it seems to describe the people before the arrival of the Numenoreans as heathens (as they were worshippers of Sauron) when landing on the shores of Middle-earth for the first time in Second Age 600. This does support the link between the Kings of Numenor and Sauron (here named Zigur), and their fall from "God's children" to beginning to build heathen temples
Then he, King (Tarcalion) landed on the shores of middle-earth, and at once he sent his messengers to (Zigur), commanding him to come in haste to do homage to the king; and he (Zigur) dissembling humbled himself and came, but was filled with secret malice, purposing treachery against the people of the Westfarers..... Thus he led astray wellnigh all the (Numenore)ans with signs and wonders.... and they built a great temple in the midst of the town (of Arminaleth) on the high hill which before was undefiled but now became a heathen fane, and they there sacrificed unspeakable offerings on an unholy altar.... Thus came death-shade into the land of the Westfarers and God's children fell under the shadow.
History of Middle-earth: Volume 9 - Sauron Defeated
Note: A heathen fane is a temple for the heathens
The above seemingly suggests that after the landing of the Numenoreans on Middle-earth, they began to fall under the dominion of Sauron and his heathendom. However, Sauron only truly starts his proper deception 2600 years later.
The kings of Numenor were not the only ones to fall into Saurons dominion. Others include the Men of the Mountains, who betrayed Isildur, "for they had worshipped Sauron in the Dark Years"(RK 5.ii.), and the race of the Black Numenoreans who, "'during the years of Sauron's domination' had 'worshipped' him" (RK 5.x.).
Now back to the Kings of Numenor. Ar-Pharazon was described as "turning back" to the worship of Sauron, suggesting that within the histories of Men, at some point they worshipped a Dark Lord and had been redeemed and have now returned.
Then Ar-Pharazôn the King turned back to the worship of the Dark, and of Melkor the Lord thereof, at first in secret, but ere long openly and in the face of his people; and they for the most part followed him.
The Silmarillion: Akallabêth
If we look through the histories of Men, this turning back can only refer to one meeting, of that between Finrod and Bëor.
But when [Finrod] questioned him concerning the arising of Men and their journeys, Bëor would say little; and indeed he knew little, for the fathers of his people had told few tales of their past and a silence had fallen upon their memory. 'A darkness lies behind us,' Bëor said; 'and we have turned our backs upon it, and we do not desire to return thither even in thought. Westwards our hearts have been turned, and we believe that there we shall find Light.'
But it was said afterwards among the Eldar that when Men awoke in Hildórien at the rising of the Sun the spies of Morgoth were watchful, and tidings were soon brought to him; and this seemed to him so great a matter that secretly under shadow he himself departed from Angband, and went forth into Middle-earth, leaving to Sauron the command of the War. Of his dealings with Men the Eldar indeed knew nothing, at that time, and learnt but little afterwards; but that a darkness lay upon the hearts of Men (as the shadow of the Kinslaying and the Doom of Mandos lay upon the Noldor) they perceived clearly even in the people of the Elf-friends whom they first knew.
It would seem from Bëor's meeting with Finrod that they had a darker past, of which they desire to forget. The Eldar began to believe that Melkor must've influenced them early in their history, and led them to worship him. This is supported in Morgoth's Ring. Which suggests that Men were to hasty and fell for Melkor's lies, worshipping him rather than the "Voice" they heard guiding them.
The first Voice we never heard again, save once. In the stillness of the night It spoke, saying: 'Ye have abjured Me, but ye remain Mine. I gave you life. Now it shall be shortened, and each of you in a little while shall come to Me, to learn who is your Lord: the one ye worship, or I who made him.'
History of Middle-earth: Volume X, Morgoth's Ring
This "Voice" seems to be Eru, informing them of their ill-decision in following Melkor and not Eru, the one true Lord.
This leaves us with four possibilities of who it could've been:
- The Kings of Numenor, under the dominion of Sauron, although this is the most likely due to there well kept history, it is unknown if taking their life early by fire was practised (especially given the desire for immortality).
- The Men of the Mountain, although their history was likely unwell kept and it's unlikely that both Gandalf and Denethor would reference them in that way.
- The Black Numenoreans, similar to the Numenorean Kings above, it is likely due to their domination by Sauron they begun these practices. Although evidence for the partaking in the practices are not given.
- The Men of Old before the meeting of the Eldar, they fell under the dominion of Melkor early on, and did not speak about their past. It is possible they practised burning themselves alive, but this part of the history of Middle-earth is unwell kept and not often spoken about.