Le TLF nous dit que c’est une forme impropre, mais la cite en effet.

E. − [Employé improprement dans une locution verbale formée d’un auxiliaire ou d’un verbe support (avoir, être, faire, prendre…) et d’un substantif abstrait désignant des « sensations ou des sentiments à l’état brut: faim, soif, froid, chaud, sommeil, mal, peur, envie, plaisir, honte, hâte… » (G. Moignet, op. cit., p. 154); emploi critiqué] Un jour, elle se retrouva dans son lit, bien faible, ayant très faim (A. France, Jocaste, 1879, p. 74). Il faut que nous fassions très attention, il faut que nous soyons très prudents (Guitry, Veilleur, 1911, iii, p. 19).

Et elle est si courante (à l’oral notamment, mais même à l’écrit) qu’elle ne choquera personne, hormis peut-être dans les contextes les plus formels.

For the “grammatical correctness” of the expression, the accepted answer is perfect. I could just add that, as a native educated speaker, I was really surprised recently to discover the expression to be incorrect.

If one slightly generalizes the question to “why do almost all native speakers feel this is correct ?”, I think the answer is in Rodney Ball’s excellent Colloquial French Grammar: A Practical Guide, section 3.1.3 (here “standard” is short for “standard French”, the rest is colloquial French.)

(d) Two further points of usage involving adjectives (and adverbs) should
be noted. Firstly, the widespread familiar use of très with certain nouns.
Expressions like j’ai très froid/très chaud are standard: froid and chaud here
are direct objects of avoir, but they are adjectives even so, and can therefore
be modified by the adverb très. Understandably enough, this causes très to
be adjoined to nouns like faim, soif or envie in the parallel expressions j’ai
très faim/très soif/très envie
(standard **j’ai grand’ faim/grand’ soif/grande envie). A further development is the still more familiar expression faire très attention (standard faire bien attention). Such uses are much criticized by normative grammarians, who see it as a breach of grammatical protocol for an
adverb to modify a noun.

J’ai faim / j’ai très faim sounds a bit like I’m starved / I’m very starved (or I’m hungry / I’m very hungry), where very as the same meaning as très. Being hungry (or starved) is a final state, while I’m starving is the beginning of the processus: je commence à avoir faim (a close meaning of je suis en train d’avoir faim, barely used).