Nouns can serve as adverbs, while retaining their noun meaning. Hence in "lightening fast" lightening is serving as an adverb to the adjective fast, but it does so by bringing its noun meaning to mind - we know that lightening is fast, and hence by picturing lightening, the adverbial intent is conveyed.
When it was first used "brand new" was the same; the audience would picture a brand fresh from the fire, and that would convey how extreme the novelty was, quite vividly.
Heavy use and less familiarity with brands themselves mean that it has lost the vividness it once had, but it is so commonly used as a phrase, that it still exists. If you don't know the imagery (that is, if you don't know why brand was chosen here), then it's no longer a noun used as an adverb, and instead it is just an adverb but only in this context.
Use of nouns as adverbs is common with colours ("fire-engine red", "apple green"). Other cases can be very vivid, but can also fall flat. The same is the case with other words used as parts of speech they don't normally serve.
One of my favourite sentences ever is from a children's book: "The ice thing only dripped and stared, and Ida mad knew goblins had been there." from Maurice Sendak's Outside Over There. Here the adjective mad is used as an adverb to modify the verb knew.
How wonderfully vivid! But do this too often and you will just confuse people. The context of a children's book also allows for rules to be stretched in different ways to other contexts*. Even in this beautiful case, the poetic license has sometimes been "fixed", as I have seen it quoted as "The ice thing only dripped and stared, and Ida mad, knew goblins had been there." where the inserted comma makes it more conventional in its grammar, but robs it of its impact as well as subtly altering the meaning.
As such, be very careful in using this sort of noun-as-adjective construct. To work well the imagery must be immediate, vivid and clear. It must also not clash badly with other imagery used elsewhere in the same piece.
*People often say "you have to understand the rules before you can break them". This is wrong. Truly, you have to understand which rules are actually tools, and how those tools help you, before you can decide that in some cases using those tools differently can help you more. The rules of good writing - even those of grammar which are stricter than those like "favour short, clear sentences" - are an example of those sort of rules, and those who "break" them poetically know not just what they gained by doing so, but have a strong understanding of what they gain in the majority of cases where they follow them.