Consider a vector $w\in\mathbb R^n$, and its orthogonal complement: $$w^\perp\equiv\left\{v\in\mathbb R^n: \langle v,w\rangle\equiv\sum_{i=1}^n v_i w_i=0\right\}.$$ I'm looking into ways to parametrise $w^\perp$.
As also discussed in Parametric equation for a plane perpendicular to a vector, the trivial way to do this is to assume one parameter to be nonzero, and remove one free parameter in the standard way. In other words, assuming e.g. $w_n\neq 0$, we have the parametrisation $$w^\perp=\left\{ t_1 e_1+ ...+t_{n-1}e_{n-1} - \frac{1}{w_n}\left(\sum_{k=1}^{n-1} w_k t_k\right) e_n: \,\, t_k\in\mathbb R \right\},$$ using $n-1$ free parameters, as expected.
This approach has, however, the downside of having to make assumptions on $w$ --- namely, it works when some coefficient is nonzero. While there is always some nonzero coefficient, this makes the solution somewhat unelegant.
A slightly different approach is given in this answer to the question linked above. The idea, as far as I understand it, is that we can quite elegantly parametrise $w^\perp$, if we accept using an overcomplete basis. This relies on the easy observation that all the vectors of the form $$v_{ij}\equiv w_i e_j - w_j e_i,$$ where $i\neq j$, satisfy $\langle v_{ij},w\rangle=0$. One can then write $$w^\perp = \left\{ \sum_{i<j} c_{ij} v_{ij} : \,\, c_{ij}\in\mathbb R \right\}.$$ This uses $\binom{n}{2}$ coefficients to parametrise an $(n-1)$-dimensional hyperplane, and thus is clearly overcomplete. Geometrically, we are writing the orthogonal complement as a linear combination of vectors that are orthogonal to the projections of $w$ on two-dimensional subspaces. From this point of view, a straightforward generalisation of the same idea would be to use as "basis" a set of vectors orthogonal to the projections of $w$ onto $k$-dimensional subspaces, for $k=2,...,n-1$.
In some comments to the question linked above, a possible link with affine/projective geometry is hinted, but not fully explored. I'm curious to know if there is a good way to understand why this type of "overparametrisation" is possible from the point of view of projective geometry, and why it doesn't require making assumptions on some coefficients, which seems to be inevitable for any parametrisation that only uses the "right" amount of coefficients.
$\newcommand{\Reals}{\mathbf{R}}\newcommand{\RP}{\Reals\mathbf{P}}$This answer aims to get at the underlying geometry rather than providing a specific method, and is long for a comment.
In the hope of meshing notation better with projective geometry, I'm bumping up the dimension, so we're looking to parametrize $n$-dimensional linear subspaces of $\Reals^{n+1}$.
Each non-zero vector $w$ uniquely determines an orthogonal complement $w^{\perp}$, and a unique line through the origin, a.k.a. a point $[w]$ of the projective space $\RP^{n}$. If we care about orientation of $w^{\perp}$, or don't want the hassle of working with equivalence classes of vectors, it's geometrically natural instead simply to normalize $w$, treating $w/|w|$ as a point of the unit sphere $S^{n}$ that spans a ray from the origin.
In my reading of the question, a parametrization is
To expand on Matthew Leingang's and my comments, and explain why over-completeness is generally needed: We can take $m = 0$ (use the "right" number of coefficients) if and only if $n = 0$, $1$, $3$, or $7$. These are the dimensions for which the sphere $S^{n}$ admits $n$ continuous vector fields $(e_{i})_{i=1}^{n}$ (which by construction may be chosen to be algebraic) whose values are linearly independent at each point. The corresponding parametrization is $$ P(w, t_{1}, \dots, t_{n}) = t_{1}e_{1}(w) + \cdots + t_{n}e_{n}(w). $$ We can also take $m = 0$ if we're willing to omit one hyperplane, or to allow our parametrization to be discontinuous at one hyperplane. For instance, away from the "north pole" $N = (0, \dots, 0, 1)$ of the sphere, we can parametrize the sphere by stereographic projection, transfer the Cartesian basis of $\Reals^{n}$ to rational tangent vector fields $(e_{i})_{i=1}^{n}$ on the sphere minus $N$, and proceed as above.
One take-away point is, the problem may be phrased in terms of finding some number of (algebraic) vector fields on the sphere whose values at each point span the tangent space.
What of over-complete parametrizations? First, there is a geometrically-natural choice with $(n+1)$ terms: For each unit vector $w = (w_{i})_{i=1}^{n+1}$, orthogonally project the Cartesian basis $(E_{i})_{i=1}^{n+1}$ into $w^{\perp}$, obtaining the spanning set $$ e_{j} = E_{j} - (E_{j} \cdot w)w = E_{j} - w_{j}w = (\delta_{ij} - w_{i}w_{j})_{i=1}^{n+1}. $$ If $t = (t_{i})_{i=1}^{n+1}$ is an arbitrary vector, the resulting parametrization is $$ v = P(w, t) = t - (t \cdot w)w = \sum_{i=1}^{n+1} t_{i}e_{i}. $$ This is closely related to the complete parametrization of the question: If some component $w_{j}$ is non-zero, then the $n$ vectors $e_{i}$ with $i \neq j$ span $w^{\perp}$, i.e., we can write $e_{j}$ as a linear combination of the $n$ remaining vectors, and eliminate the term $t_{j}e_{j}$ from the preceding sum.
In $\Reals^{3}$, writing $w = (x, y, z)$, this becomes \begin{align*} e_{1}(w) &= (1 - x^{2}, -xy, -xz), \\ e_{2}(w) &= (-xy, 1 - y^{2}, -yz), \\ e_{3}(w) &= (-xz, -yz, 1 - z^{2}). \end{align*}
The over-complete parametrization of this question, i.e., Did's answer in the linked question, instead uses the $\binom{n+1}{2}$ vectors $e_{ij}(w) = w_{i}e_{j} - w_{j}e_{i}$ with $1 \leq i < j \leq n+1$. If $t = (t_{i})_{i=1}^{n+1}$ is a vector in $\Reals^{n+1}$, then $0 = t \cdot e_{ij}$ for all $i$, $j$ if and only if $0 = w_{i}t_{j} - w_{j}t_{i}$ for all $i$, $j$, if and only if $t$ is proportional to $w$. That is, the vectors $(e_{ij}(w))$ span $w^{\perp}$.
In $\Reals^{3}$, as gIS (OP) notes in the comments, this becomes \begin{align*} e_{23}(w) &= (0, z, -y), \\ e_{13}(w) &= (z, 0, -x), \\ e_{12}(w) &= (y, -x, 0). \end{align*}
I'm not the right person to give a detailed algebro-geometric picture, but the incidence problem for a vector lying in a hyperplane may be formulated like this: If $t$ and $w$ are non-zero vectors, then $t \in w^{\perp}$ if and only if $0 = t \cdot w = \sum_{i} t_{i}w_{i}$. For algebraic geometry, it's preferable to view $t \in \Reals^{n+1}$ and $w^{\perp}$ as an element of the dual space $(\Reals^{n+1})^{*}$. Either way, the incidence condition is invariant under multiplication of either factor by non-zero scalars, so is "naturally" viewed as a quadric hypersurface in the product of projective spaces $\RP^{n} \times \RP^{n}$.
The parametrization question may be viewed as seeking an embedding of this quadric in a larger-dimensional projective space, with lower-degree and lower-dimensional embeddings preferred for simplicity. As the two examples above show, however, there are trade-offs: The first has linearly-many vectors ($n+1$ for an $n$-dimensional space) whose components are quadratic in $w$, while the second has quadratically-many vectors ($\frac{1}{2}n(n+1)$ for an $n$-dimensional space) whose components are linear in $w$.