Algebraic account of Gaussian elimination?
You really should read Gowers' essay carefully - it cleanly details the reasons why you need a basis in general. So if there is going to be an algebraic account of Gauss-Jordan, it will necessarily involve some additional conditions.  You can get an idea of the kinds of conditions by reading the n-lab page on dual vector spaces.  There it shows that there are a lot of spaces which are isomorphic to their double duals.

As you mention, this is related to double-negation elimination.  But let's spell that out. The isomorphism is linear CPS transform, as it is the set of functions $\left(V\multimap R\right)\multimap R$. You are seeking `unCPS'. Which highlights how miraculous the structure of $V$ must be for this to be feasible at all.  The page on the n-lab gives some of these miracles. [Turns out that, syntactically, this works for the duality measure $\leftrightarrow$ linear functional on programs if you choose your programming language "just right"; if you're curious, see my work with Chung-chieh Shan at PADL 2016, where we implement $\texttt{unCPS}$].

Another way, more computational, to look at this is to look at more general versions of LU decomposition. For LU with full pivoting, you can decompose $A$ as $PAQ = LDU$ with $P$ and $Q$ as permutation matrices, $D$ diagonal, $L$ unit lower triangular and $U$ unit upper triangular. You can generalize even more to various kinds of rings (see Fraction free factors by Zhou and Jeffrey). The point is that $P$ and $Q$ are arbitrary, but $L,D,U$ depend on them -- another way to see the base dependence. Clever choices of $P$ and $Q$ allow you to deal with whatever defects the expression of $A$ in the original basis were, and 'rotate' things in better position -- be it for stability, sparsity, expression size blowup, etc.