Believe as a noun

I've never come across this particular example either, but it is a general truth in English that words do not have fixed grammatical functionality as they do in most other languages. For example, the world 'table' in French IS and MUST BE a noun, but in English we already commonly use it as either a noun or verb and we may use it pretty much any way we like and be understood. In the expression "table tennis" for example, it's being used as an adjective. English so easily enables this function-switching that we are immediately understood when we invent new uses, such as "Oh, that's very Lady Di" (using a proper noun as an adjective).

Well, the verb "tabler" does exist in French but, in general terms, you are right.

There are two aspects of English that allow this ease in "function-switching":

1. The minimal inflection of most English verbs. To make a word usually used as a noun into a verb requires no great modification beyond the addition of "-(e)s", "-(e)d" or "-ing" in some circumstances. In French, one must first assign the word to one of the three possible conjugations and then go from there with the appropriate endings (this is fairly common though).

2. Noun to adjective function-switching is a common Germanic trait - we see it in German with those massive compound nouns, e.g, "Kontactlinseverträglichkeitstest"
but in fact we have the same thing in English except that we place spaces between the words in writing. If we did not, the English equivalent of the long German noun above would be just as endless: "contactlenscompatibilitytest".

(Yes, I know, some glitch is inserting a carriage return in that German word; "test" should not be separated from the rest of the word. Beats me!)

If 'table' in 'table tennis' is an adjective, is 'tooth' an adjective in toothpaste?

'table tennis' is an example of a compound noun, not a noun being used as an adjective. I make this claim because an adjective supposedly 'describes' a noun. In the case of a compound noun, a new, single, unmodified thing is named by combining two nouns. Sometimes, as with toothpaste, they end up as a single word. Sometimes they remain as two words long enough for one of the words to develop adjectival colors. The best way to tell if the latter has happened is to see if it is possible to apply the proto-adjective to other, unrelated nouns.

Take 'football'. A game, or an object used in the game of the same name. Does ball describe foot or foot describe ball? Doesn't really matter. Add an (accepted) adjective:

"wet football" - the ball, or the game, has been rained on.

"table football" - oooh! 'table' in the place of 'wet'. Is it an adjective?

"I'm all wet." - adjective.

"I'm all table." - utter drivel.

The german convention of not leaving spaces in compound nouns avoids the issue of mistakenly identifying an adjective in this way.

To look at it another way (quantized):

"Lets go and play table tennis."

Am I saying "lets go and play the game called 'table tennis'", or am I saying "lets go and play tennis in some way that can be described as 'table'" ?

The former takes "table tennis" as a single quantum - the name of a game; the latter takes "table tennis" as two quanta - the game of tennis (1) described as 'table' (2).

If the latter is what you meant, then table is being used adjectivally; if the former, then it is being used as part of a compound noun.

I've tried to make this argument without recourse to Platonic ideals, but I might, if pressed.

Tolken, I think you're presenting a false dichotomy. Nouns are used as adjectives all the time in English. Adjectival phrases including nouns also modify other nouns. Compound words may be made up of nouns used as adjectives modifying other nouns. They can be both. They're two different paradigms. Something can be both a compound word AND made up of two nouns, one of which is adjectivally modifying the other. While we're at it, Compound nouns don't have to be made up only of nouns. They can be made up of plain old adjectives modifying nouns. There are even compound verb-verb combinations that are nouns.

This should be especially obvious in the examples you gave, as they are all endocentric compounds:

Table tennis, is a kind of miniature tennis that is, uh, played on a table. Football is a game where you kick a ball with your, uh, foot. Toothpaste isn't just any paste. It's a paste that you use to clean your, uh, teeth, yes?

Animal doctor, horse fly, etc. etc.