Having had some more time to think about this, I realized that I've unnecessarily confused myself, and that I'd been trying to prove $A^tA = [g(f_i,f_j)]$ in the pseudo-Riemannian case, which is actually incorrect. The fix however, is very simple. For fun, I'll include the modified statement, along with two proofs.
Theorem.
Let $(V, g, \mathcal{Or})$ be an $n$-dimensional, oriented, pseudo inner-product space over $\Bbb{R}$. Then, there is a unique volume form $\omega$ on $V$, such that for every positively-oriented, ordered, $g$-orthonormal basis $\{e_1, \dots, e_n\}$ of $V$, we have
\begin{align}
\omega(e_1, \dots, e_n) &= 1.
\end{align}
The first proof makes use of the fact that a (pseudo) inner product, $g$, on $V$ induces for each $q \in \Bbb{N}$, a pseudo-inner-product $g_q$ on the subspace $\mathcal{A}^q(V)$ of alternating $q$-tensors over $V$.
Proof $1$.
Let $\{e_1, \dots, e_n\}$ be a positively oriented, $g$-orthonormal basis of $V$, and $\{\epsilon^1, \dots, \epsilon^n\}$ the dual basis. Suppose that the number of $-1$ in the matrix $[g(e_i,e_j)]$ is $\#$. Then,
\begin{align}
g_n\left( \epsilon^1 \wedge \dots \wedge \epsilon^n, \epsilon^1 \wedge \dots \wedge \epsilon^n\right) &= \det\bigg( g_1\left(\epsilon^i, \epsilon^j\right)\bigg) = \det\bigg( g\left(e_i, e_j\right)\bigg) = (-1)^{\#}
\end{align}
If $\mu$ is any other volume-form, which satisfies $g_n(\mu, \mu) = (-1)^{\#}$, then since $\mathcal{A}^n(V)$ is one-dimensional, there is a $c\in \Bbb{R}\setminus\{0\}$ such that $\mu = c \cdot \epsilon^1 \wedge \dots \wedge \epsilon^n$. Then
\begin{align}
(-1)^{\#} &= g_n(\mu, \mu) = c^2 g_n(\epsilon^1 \wedge \dots \wedge \epsilon^n,\epsilon^1 \wedge \dots \wedge \epsilon^n) = c^2 (-1)^{\#}.
\end{align}
Hence, $c^2 = 1$, so $c = \pm 1$, which means $\mu = \pm \epsilon^1 \wedge \dots \wedge \epsilon^n$.
In particular, if $\{f_1, \dots f_n\}$ is a positively oriented, $g$-orthonormal basis of $V$, and $\{\varphi^1, \dots, \varphi^n\}$ its dual basis, then
\begin{align}
\varphi^1 \wedge\dots \wedge\varphi^n &= \pm\epsilon^1 \wedge \dots \wedge \epsilon^n;
\end{align}
but in fact since both bases are positively-oriented, it is easily shown that the volume forms induced by them must be proportional by a positive constant. Hence,
\begin{align}
\varphi^1 \wedge \dots \wedge\varphi^n = \epsilon^1 \wedge \dots \wedge \epsilon^n. \tag{$*$}
\end{align}
Hence, we can define $\omega := \epsilon^1 \wedge \dots \wedge \epsilon^n$, and the above argument shows that this definition is independent of the choice of basis. Lastly, it is clear that
\begin{align}
\omega(e_1, \dots, e_n) = (\epsilon^1 \wedge \dots \wedge \epsilon^n)(e_1, \dots, e_n) = 1,
\end{align}
which completes the proof of both existence and uniqueness of $\omega$.
The second proof establishes more in the process:
Proof 2.
Let $E = \{e_1, \dots, e_n\}$, $F = \{f_1, \dots, f_n\}$ be positively-oriented, ordered, bases for $V$, and we assume that $E$ is $g$-orthonormal. Also, let $E^* = \{\epsilon^1, \dots, \epsilon^n\}$ and $F^* = \{\varphi^1, \dots, \varphi^n\}$ be the respective dual bases for $V^*$. Lastly, let $T:V \to V$ be the isomorphism such that $f_j = T(e_j)$, for all $j \in \{1, \dots, n\}$. Then, we have the following relations between the various matrix-representations:
\begin{align}
[g]_F &:= [g(f_i, f_j)] \\
&= [g(T(e_i), T(e_j))] \\
&= \left([T]_E \right)^t \cdot [g]_E \cdot [T]_E \tag{basic linear algebra}
\end{align}
Hence, by taking the determinant of both sides, and using elementary properties of the determinant, we find that
\begin{align}
\det [g]_F &= (\det T)^2 \cdot \det [g]_E
\end{align}
Since $E$ is a $g$-orthonormal basis, we have that $\det [g]_E = \pm 1$. It follows that
\begin{align}
|\det(T)| &= \sqrt{\left|\det [g]_F \right|}
\end{align}
Also, one of the definitions of $\det T$ is that it is the unique constant such that
\begin{align}
\epsilon^1 \wedge \dots \wedge \epsilon^n &= (\det T) \cdot \varphi^1 \wedge \dots \wedge \varphi^n
\end{align}
Since we assumed $E$ and $F$ are positively-oriented, it follows that the volume forms they induce must be proportional by a positive constant. Hence, it follows that
\begin{align}
\epsilon^1 \wedge \dots \wedge \epsilon^n &= \sqrt{\left|\det [g]_F \right|} \cdot \varphi^1 \wedge \dots \wedge \varphi^n.
\end{align}
From this formula, it follows that if we further assume $F$ is $g$-orthonormal, then the determinant on the RHS is $1$, so we obtain exactly the same relationship as in $(*)$ of proof 1. Therefore, we can define
\begin{align}
\omega &:= \epsilon^1 \wedge \dots \wedge \epsilon^n,
\end{align}
and this definition is basis-independent. The fact that $\dim \mathcal{A}^n(V) = 1$ shows that $\omega$ is unique.
I found proof $1$ more conceptually clear: the pseudo-inner product $g$ induces one on every space of alternating tensors, and by using the fact $\dim \mathcal{A}^n(V) = 1$, it follows that there are exactly two volume forms which are "normalized", to $(-1)^{\#}$, and these volume forms only differ by a sign. Then, the orientation $\mathcal{Or}$ helps us to pick one of these two volume forms.
The second proof is more "down-to-earth", but necessarily more computationally tedious, because it doesn't require us to define the inner product on each space of alternating tensors (that by itself requires a little bit of work to show everything is well-defined etc). It only requires basic linear algebra, and knowing the relationship between the determinant and wedge products to prove that $\omega$ is well-defined and unique.
One advantage though is that for computational purposes, it gives us an explicit formula for the volume element, in terms of any positively-oriented basis. Such a formula could potentially be useful in certain concrete situations, for example, when performing integration on manifolds, and choosing a chart which is particularly suited to the specific problem at hand. In such a case, orthogonalizing, or normalizing the tangent vectors in the might be more tedious than simply calculating a determinant (for example, the tangent vectors in the spherical-coordinate chart are not normalized).
