Yes, every curve parametrized by $[0,1]$ has an irreducible parametrization, and your ideas for proving this are mostly correct.
You have a lot of good ideas mixed in with a few that won't quite fly, but luckily the correct ideas are enough. That is, we can still make your inductive property approach work.
The problems.
The problematic part of your outline is that you don't know that you can decompose into countably many disjoint closed intervals in the way you describe. That is, even when $n=1$ and you consider the Cantor function, this function is constant on a countable union of intervals, and what is left over is not a countable union of closed intervals - rather it is a Cantor set. For the same reason your property $P$ is not inductive, as the Cantor set arises as an intersection of nested finite unions of disjoint closed intervals.
The easy part.
Firstly, we should get the easy part of the proof out of the way. Let $t\in[0,1]$ be the minimum value (which exists by compactness) such that $\gamma([0,t])=C$, then let $s\in[0,t]$ be the maximum value such that $\gamma([s,t])=C$. Without loss of generality we will take $s=0$, $t=1$, as we may certainly restrict and reparametrize $\gamma$ to ensure this. Then $\gamma([a,b])\neq C$ for any proper closed interval $[a,b]\subset [0,1]$.
It can be verified easily throughout the rest of this proof that none of our subsequent reparametrizations change this fact, and so we leave it to the reader to keep us honest while we find a reparametrization $\gamma_0$ such that $\gamma_0([0,1]\backslash (a,b))\neq C$ for all proper subintervals such that $\gamma_0(a)=\gamma_0(b)$.
Defining $P$ correctly.
Now define $P(X)$ to be the property that $X\subseteq [0,1]$ is closed, satisfies $\gamma(X)=C$, and satisfies $\gamma(a)=\gamma(b)$ for each component $(a,b)$ of $[0,1]\backslash X$.
We claim $P$ is inductive. To see this, suppose $X_i\supseteq X_{i+1}$ is a decreasing sequence with this property. Then certainly the intersection $X=\cap_{i=1}^\infty X_i$ is closed and satisfies $\gamma(X)=C$ (the latter can be seen from the fact that for each $c\in C$ the sets $\gamma^{-1}(\{c\})\cap X_i$ are nonempty, and so give a nested sequence of nonempty compact sets).
It remains to show that $\gamma(a)=\gamma(b)$ for each complementary interval $(a,b)\subseteq [0,1]\backslash X$. To see this, we suppose $0<\epsilon<\frac{b-a}{2}$. Denote $U_i=[0,1]\backslash X_i$, so that $\bigcup_{i=1}^\infty U_i=[0,1]\backslash X$. The sets $U_i$ form an open cover of $[a+\epsilon,b-\epsilon]$, hence have a finite subcover, which by monotonicity can consist of a single $U_i$. Then if $(a',b')$ is the component of $[a+\epsilon,b-\epsilon]$ in $U_i$, then since $U_i\cap X=\emptyset$, we have $$[a+\epsilon,b-\epsilon]\subseteq (a',b') \subseteq (a,b),$$
so that $a'\in [a,a+\epsilon)$ and $b'\in (b-\epsilon,b]$. Since $\gamma(a')=\gamma(b')$, letting $\epsilon\to 0$ gives $a'\to a$ and $b'\to b$, so we have $\gamma(a)=\gamma(b)$ by continuity of $\gamma$.
Completing the proof.
Having established that $P$ is inductive, let $X$ have property $P$ irreducibly, as per Brouwer's Theorem.
Your idea now works perfectly. Define $\gamma'$ to equal $\gamma$ on $X$ and to equal the common value $\gamma(a)=\gamma(b)$ constantly on every complementary component $(a,b)\subseteq [0,1]\backslash X$. Observe that if $[a,b]\subset [0,1]$ is any proper subinterval with $\gamma'(a)=\gamma'(b)$, and $(a,b)\cap X\neq\emptyset$, then $$\gamma'([0,1]\backslash (a,b))=\gamma(X\backslash (a,b))\neq C,\tag{1}$$ since otherwise we could let $X'=X\backslash (a,b)$ and obtain a smaller set with property $P$.
Now let $\gamma_0$ be a light mapping such that $\gamma' = \gamma_0\circ m$ for some monotone increasing surjection $m\colon [0,1]\to [0,1]$.
To complete the proof we must show that $\gamma_0([0,1]\backslash (a,b))\neq C$ for any proper subinterval $[a,b]$ with $\gamma_0(a)=\gamma_0(b)$. To see this, observe first that if we let $(a',b')=m^{-1}((a,b))$, (note that the inverse image of an interval under a monotone map is another interval), then we must have $(a',b')\cap X\neq\emptyset$, as otherwise $\gamma'$ is constant on $(a',b')$, implying by lightness of $\gamma_0$ that $m$ is constant on $(a',b')$, so that $m((a',b'))\neq (a,b)$, contradicting surjectivity of $m$.
But then we have $\gamma'(a')=\gamma'(b')$ and so from (1) we obtain $$\gamma_0([0,1]\backslash (a,b))= \gamma_0(m([0,1]\backslash (a',b')))=
\gamma'([0,1]\backslash (a',b'))\neq C.$$
Best Answer
There are counter examples when one of the functions is locally constant. Take the case where $f$ is monotone and in a neighborhood of $x=\frac{1}{2}$ we have $f(x)=\frac{1}{2}$ locally constant and $g(x)=(x-\frac{1}{2})\sin\left(\frac{1}{x-1/2}\right)$. If we had such $\phi_1,\phi_2$ as desired, we could find some $t_0$ satisfying $\phi_2(t_0)=\frac{1}{2}$, then as $t\to t_0$ we have $g(\phi_2(t))$ oscillating above and below $\frac{1}{2}$ infinitely often, so likewise so does $f(\phi_1(t))$. Since $f$ is monotone and locally constant around $\frac{1}{2}$ however, this implies $f(\phi_1(t))$ is infinitely often above and below that neighborhood of local constancy, a contradiction of continuity.
This is a known problem, and the corresponding question for when $f,g$ are restricted to never be locally constant has been shown to be true in the affirmative. In this paper by John Philip Huneke, it is proven in their Lemma 2 that the the functions $\phi_1,\phi_2$ do always exist. Credit to Gerry Myerson for bringing this to my attention in the comments.