Disclaimer: I am not an expert in logic nor in mathematics in general, so please feel free to correct me in any of my assumptions or statements below.
Gödel's Incompleteness Theorem states that "any consistent formal system $F$ within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of $F$ which can neither be proved nor disproved in $F$."
Let me assume mathematics, as we use it in any field, is a formal system (I am purposely omitting the term "consistent" here), then, by Gödel's Incompleteness Theorem, it might be the case that any of the Millennial Problems like the Riemann Hypothesis or P vs NP are statements which can neither be proved nor disproved within mathematics as we know it.
Therefore one may has to come up with a completely new style of "mathematics" which no one has ever thought of before to prove or disprove any of the given problems, is this correct?
Furthermore, since Gödel's Second Incompleteness Theorem states that $F$ can never prove its own consistency (i.e. $F \nvdash Cons(F)$), this would imply that non of mathematics is actually consistant (otherwise we are talking about a snake biting its own tail) and it can never be proved.
Therefore Gödel's Second Incompleteness Theorem shows us that there cannot exist an interpretation or a theory of mathematics that does not only universally hold true but holds and indeed is total truth.
To get all of this to a more practical point of view: Would this imply that the search for a "world formula" or some kind of "unified field theory" in physics (like String Theory) is pointless because we will never be able to find the total truth behind everything?
Does this mean that all of mathematics is nothing else than the greatest childs playground in the history of all mankind where we can define our own rules and just play according to these rules? ... and if they do not fit our needs, we just create new ones? ... and physics simply tries to find connections and approximations between this illusion of correctness and trust we have in mathematics to the real world?
"Therefore one may has to come up with a completely new style of "mathematics" which no one has ever thought of before to prove or disprove any of the given problems, is this correct?"
In a sense, but probably not in the sense that you might imagine. Note that Gödel's theorem requires the natural numbers. This implies that problems of Mathematics related to the theorem necessarily hinge on the concept of infinity.
Statements involving infinity generally don't have a "truth value" in the sense that we imagine them, where "I'm wearing a blue shirt" is thought of as being "false" and "I'm wearing black shirt" is thought of as being "true". I think that the best way to interpret Gödel's theorem is that statements involving infinity instead only have a "provable value". Either the statement is (dis)provable in your system, or it is not. "True" and "false" never enter into it, because infinity, as we use it in math, is an abstract concept, and statements involving it aren't "real" in the sense that my shirt is real.
As a general rule, if a particular statement about infinity is not provable or disprovable within your system, and you happen to need that statement for some reason or another, you simply adopt it into your system. Thus, the extra machinery isn't generally anything deeper than the statement of the problem itself. Notice that we already do this with various statements that are convenient but not provable within the ordinary formalism of math (a very common one is "ZF", for Zermelo-Fraenkel set theory). One popular one is the Axiom of Choice. It's not provable or disprovable within ordinary ZF, but some authors adopt it for convenience. Another one is the Continuum Hypothesis.
Setting out to introduce the machinery to prove the Axiom of Choice is moot, because the machinery to prove the Axiom of Choice is simply "assume the Axiom of Choice".