It is true that all non-MDS $(n,k)$ codes contains at least one $k$-sized coordinate subset that does not correspond to an information set (because all such subsets are information sets iff the code is MDS by definition).
What I want to prove is that each coordinate of a non-MDS code constitutes a non-information set when appended with some $k-1$ sized subset of other coordinates. I think I've proved it for linear codes:
For linear codes we have that the non-zero positions of a vector $\boldsymbol{\alpha}$ correspond to a non-information set if $\sum_{i=1}^n \alpha_i = k$ and $\boldsymbol{\alpha}G = \textbf{0}$, i.e. $\sum_{i=1}^n \alpha_i \mathbf{c}_i = \textbf{0}$.
Assume that there exists a column $\mathbf{c}_x$ such that it forms a basis when combined with any other $k-1$ columns in $G$. WLOG, assume $\mathbf{c}_x = \mathbf{c}_1$. If $\mathbf{c}_1+\sum_{i=2}^k \alpha_i \mathbf{c}_i = \mathbf{c}_{k+1}$, then we require all $\alpha_i =1$, otherwise $\mathbf{c}_1$ would be in the span of some other $k-1$ columns. But in the same vein, we would also require $\mathbf{c}_1+\sum_{i=2}^k \mathbf{c}_i = \mathbf{c}_{k+2}$, which would mean $\mathbf{c}_{k+1} = \mathbf{c}_{k+2}$, which would mean that we can choose $\mathbf{c}_1,\mathbf{c}_{k+1},\mathbf{c}_{k+2}$ along with $k-3$ other columns, which means we have $k$ columns that do not form a basis. This leads us to the conclusion if $n \geq k+2$, all coordinates are part of some non-information set. (Note that if $n<k+2$ then we have no contradiction because an MDS code is possible to construct)
An information set of a non-linear code can be defined as any $k$ column indices forming a $2^k \times k$ submatrix of the $2^k \times n$ codebook matrix such that no two rows are identical. This definition coincides with the submatrix rank definition when applied to linear codes. Does anyone have any ideas on how to proceed in the nonlinear case?
(A verification of my thought process in the linear case would be nice as well)