As I remember, Tolkien mentions him in The Silmarillion. He says, that at the time when ME lied in darkness lit by stars only and children of Eru woke up he was walking here and there...
My opinion is that Bombadil is the first Stuart of ME, he was left behind by Vallar when they left to the West in order to keep eye on ME and guide first elves (and may be men). His ability to give orders to trees, to make roads in the wood can be useful to direct elves to the West. Later he retired to a small corner of ME and kept it unchanged as a kind of national park
When Gandalf says they are alike, I believe, he means the stuartship. Bombadil's powers make me think he was a Maia.