This leaves just two serious theories to consider. One, that Bombadil is a Maia (or an "unaffiliated" Ainu), presumably one not named specifically elsewhere in the texts. The other, that Bombadil is some sort of nature spirit of a type never explicitly mentioned in Tolkien's writings after LotR. Each of these has advantages and disadvantages, and I do not believe that we have enough information to decide between them. The two may not be entirely distinct (some minor Maiar might be well described as "nature spirits"), but we will treat them separately below.
Bombadil as a Maia
We begin by considering the theory that Bombadil is one of the Maiar. In this essay the term "Maia" will refer to any of the Ainur who entered Ea other than the Valar. This may be an abuse of language: Tolkien defines "Maiar" in the "Valaquenta" when writing of "servants and helpers" of the Valar, but some Ainur could have entered Ea entirely unaffiliated with the Valar and their labors (Bombadil displays no clear affiliation). As the following discussion does not distinguish between them, I treat both cases together. I have chosen to use the term "Maia" rather than "Ainu who is not a Vala" mostly for convenience, but also because it is the most common claim of this sort. Note that under this definition a "Maia" could potentially be as powerful as the lesser Valar.
Arguments Favoring Bombadil as a Maia
The primary argument for the theory that Bombadil is a Maia is a simple process of elimination: of all the sentient "races" explicitly named in canonical texts, the only group we have not ruled out is the Maiar. This is a very familiar argument, but despite the criticisms and alternate suggestions discussed below its strength cannot be emphasized enough: any other claims about Bombadil's nature are in a way presumptuous, as they require us to add new dimensions to Middle-earth without direct support in Tolkien's canonical writings.
While few Maiar are named or described in The Silmarillion or Tolkien's other writings, there are many indications that their numbers were very great. The "Valaquenta" makes this clear: "Their number is not known to the Elves, and few have names in any of the tongues of the Children of Iluvatar". Thus, while Bombadil is not named in The Silmarillion and is not similar to any of the Maiar described there, that in no way proves he was not one of them.
In addition to these general arguments, there is at least one quote that suggests more directly that Bombadil may be a Maia. In the chapter "Homeward Bound" in LotR, Gandalf tells the hobbits that he is
"going to have a long talk with Bombadil: such a talk as I have not had in all my time. He is a moss-gatherer, and I have been a stone doomed to rolling. But my rolling days are ending, and now we shall have much to say to one another."
Gandalf's words suggest a kinship between the two (but certainly do not prove one). In particular, the second sentence could indicate that the main difference between Gandalf and Bombadil was their role in world affairs: active or passive, respectively. As we know that Gandalf is a Maia (in a special situation, to be sure), this would suggest that Bombadil is one as well.
Bombadil also interacts with the Ring in surprising ways. It does not make him invisible, he is able to make it invisible, he sees Frodo wearing it, and Frodo is able to hand it to him without a second thought. If Tom were a powerful Maia (or other very powerful being) with active power over the Ring then all this is easily explained. However, passive explanations that do not require Tom to be particularly powerful exist as well, and Gandalf advocates a passive view at the Council of Elrond: "Say rather that the Ring has no power over him." To decide between these possibilities we would need a much greater understanding of the Ring; without that, this evidence is of little use.
This theory gives an easy explanation for Goldberry as well: if Bombadil is a Maia, Goldberry is almost certainly the same. In some ways, she fits that role even better than Bombadil: her affinity for the Withywindle and her many songs about it would be very natural if it had been her main contribution to the Music of the Ainur. More broadly, Tom and Goldberry's frequent singing might reflect their memory of being part of the original Music.
Objections to Bombadil as a Maia
Despite this strong case for the theory that Bombadil is a Maia, there are questions that it leaves unanswered. To begin with, Tom tells the hobbits, "Eldest, that's what I am." This seems to be an important clue to Bombadil's nature, and is repeated at least twice at the Council of Elrond: Elrond tells us that Bombadil's Elvish name "Iarwain Ben-adar" means "oldest and fatherless", and as quoted earlier Glorfindel says that Tom would be "Last as he was First".
What could "Eldest" or "First" mean for one of the Ainur? Only three answers seem reasonable: that Bombadil was the "first" Ainu created by Iluvatar, the first Ainu to enter Ea, or the first Ainu to reach Arda or Middle-earth. However, none of these seem consistent with Glorfindel's word "Last": Sauron at least would remain after Bombadil was gone.
Related is Tom's claim (from "In the House of Tom Bombadil") that "He knew the dark under the stars when it was fearless--before the Dark Lord came from Outside." This almost certainly refers to Melkor (the dark was never truly fearless once he set his evil in motion), but it could refer to his original arrival in Ea or to his return to Arda from the "outer darkness" in the days of the Lamps. The former interpretation might suggest that Bombadil was present in Ea before any of the Ainur arrived, although such a reading is not necessary.
Another question left unanswered by the claim that Tom is a Maia is his indifference to the Ring. As Gandalf says in the Council of Elrond, "if he were given the Ring, he would soon forget it, or most likely throw it away. Such things have no hold on his mind." This attitude is entirely opposite that of all the other Maiar involved with the Ring in the book: Sauron, Saruman, Gandalf, and conceivably even the Balrog are all strongly drawn to the Ring. More generally, even the Valar sometimes fell victim to Morgoth's plots, and the Ring may have provided abilities that even a very powerful Ainu could lack.
Why, if Bombadil is a Maia, is he not tempted by the Ring? Speaking of Bombadil, Tolkien says in Letter #144 that
"if you have, as it were taken 'a vow of poverty', renounced control, and take your delight in things for themselves without reference to yourself, watching, observing, and to some extent knowing, then the question of the rights and wrongs of power and control might become utterly meaningless to you, and the means of power quite valueless."
To avoid the lure of the Ring, such a "vow" must be absolute. Even those who simply desire to observe and understand the things around them can be tempted by power. As a scientist, for example, the Ring might tempt me with visions of how much we could learn about the world if more people were excited by the quest for knowledge. Bombadil somehow overcomes all such temptations effortlessly. It seems impossible that any human could be so successful, and it is difficult to believe that any of the Ainur would be entirely unaffected. This is not proof that Tom is not a Maia, but that theory leaves the question of his immunity to the Ring unanswered.
There is also at least one argument against the idea that Goldberry is one of the Maiar. Goldberry is consistently called names like "daughter of the River", but it is not at all clear in what sense this could describe a Maia. In particular, a Maia whose part in the Music of the Ainur focused on the Withywindle would more appropriately be called its "mother" than its "daughter". I have found no good way to reconcile this language with the Maia theory.