[Inderjit Sanghera]

I think Tom Bombadil's reference to his coming before the Dark Lord, was a description of Melkor's return to Arda after he was driven out my Tulkas. There were no Evil creatures around then (except those secretly under the rule of Morgoth, like Sauron), during the Spring of Arda,and so his quote about knowing the Earth under the stars, before fear, could be equated to the Spring of Arda,before Melkor came, as I don't think the Earth was fully wrought when he was driven out.