Note: So that there is no confusion: with maximal independent set, I do not mean the maximum independent set in $G$. A maximal independent set $I$, is an independent set, which cannot be extended by any vertex of $V(G)\setminus I$ without violating independence of $I$. $I$ is not necessarily the maximum independent set in $G$.
Theorem: Every graph $G$ contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set in $G$.
Under the assumption that there are graphs with a minimum coloring that do not have a maximal independent set, we can easily show that there is an equivalent minimum coloring that does have maximal independent set.
Proof: Let $G=(V,E)$ be any graph with chromatic number $\chi$. Suppose $G$ is properly colored, then we have a set $S=\{I_0,I_1,\cdots,I_{\chi-1}\}$ of independent sets in $G$ with $I_0 \cup I_1 \cup \cdots \cup I_{\chi-1}=V(G)$. If $\exists I \in S$ which is maximal, we are done. If $\nexists I \in S$ which is maximal, we arbitrarily pick an independent set $I'\in S$ and for each $v \in V(G) \setminus I'$ we remove $v$ from its independent set and assign it to $I'$ if $v$ has no neighbors in $I'$, making $I'$ a maximal independent set. Lastly, we color $v$ with the color of $I'$.
I think that every valid minimum coloring of a graph $G$ contains at least one maximal independent set. It can be easily shown using the greedy algorithm, since it constructs maximal independent sets by design. But in my opinion this is not sufficient, since how could we know that there isn't an algorithm which does it differently. How do I proof that every valid minimum coloring of a graph $G$ contains at least one maximal independent set?
Not all minimum colorings contain a maximal independent set as one of the color classes.
For example, take this graph:
You can color it with $3$ colors so that every color class has $2$ vertices. None of those are maximal: you can take any independent set of $2$ vertices, and add one of the three outside vertices to it.
However, you also don't need to make any claims about all colorings in order for the proof to work. You pick an arbitrary coloring. If it has a color class which is a maximal independent set, you're done. If not, you can make it bigger - as you describe - until it is.