For $n=3$, a spherical polygon's area is given by the Gauss-Bonnet theorem:
$$|A|=2\pi-\sum_{i=1}^m\phi_i$$
$$=\sum_{i=1}^m\theta_i-(m-2)\pi$$
where $\theta_i$ is the interior angle and $\phi_i$ is the exterior angle (both tangent to the sphere) at the $i$th vertex; $\theta_i+\phi_i=\pi$.
Each angle $\phi_i$ is the angle between the planes defining the two edges. In terms of the vectors $a_i\in\mathbb S^2$ representing the vertices, the angles are given by
$$\cos\phi_i=-\cos\theta_i=\frac{-(a_{i-1}\wedge a_i)\cdot(a_i\wedge a_{i+1})}{\lVert a_{i-1}\wedge a_i\rVert\cdot\lVert a_i\wedge a_{i+1}\rVert}=\frac{(a_{i-1}\times a_i)\cdot(a_i\times a_{i+1})}{\lVert a_{i-1}\times a_i\rVert\cdot\lVert a_i\times a_{i+1}\rVert}$$
or in terms of the planes' normal vectors,
$$=v_{i-1}\cdot v_i.$$
But this doesn't tell us whether $\phi_i$ is positive or negative; for that we also need
$$\sin\phi_i=a_i\cdot(v_{i-1}\times v_i)=-I(a_i\wedge v_{i-1}\wedge v_i)=(-Ia_i)(v_{i-1}\wedge v_i)$$
where $I=e_1e_2e_3$. (I'm using the language of geometric algebra.) Likewise, $\sin\phi_i$ alone doesn't tell us whether $\phi_i$ is acute or obtuse. To uniquely determine $\phi_i$, the two formulas can be combined into
$$\exp(Ia_i\phi_i)=\cos\phi_i+Ia_i\sin\phi_i=v_{i-1}v_i.$$
The polygon's perimeter $|\partial A|$ is the sum of the angles $\beta_i$ (cutting through the centre of the sphere) between consecutive vertices. These are given by
$$\exp(-Iv_i\beta_i)=\cos\beta_i-Iv_i\sin\beta_i=a_ia_{i+1}.$$
In your case, $A$ is (the complement of?) a convex polygon, so all $\phi_i$ have the same sign, and thus
$$|A|=2\pi\mp\sum_{i=1}^m\arccos(v_{i-1}\cdot v_i).$$
(Of course we define $v_0=v_m$.) If the set $\{v_i\}$ is unordered so $v_{i-1}$ is unknown, then you can determine whether $v_i$ and $v_j$ are adjacent by whether $v_i\times v_j$ is contained in all the other half-spaces.
For general $n$, I'm thinking of using the divergence theorem to reduce the integral over the polytope to an integral over its boundary. This would require finding a vector field $F$ on the sphere with divergence $1$:
$$|A|=\int_Ad^{n-1}x\overset?=\int_A(\nabla\cdot F)\,d^{n-1}x=\oint_{\partial A}({\bf n}\cdot F)\,d^{n-2}x$$
(${\bf n}$ is the unit vector tangent to the sphere and normal to $\partial A$. For your polytope, this is ${\bf n}=v_i$ on each part of the boundary.)
Using spherical coordinates, here's one example of such a vector field:
$${\bf x}=(\cdots((e_1\cos\theta_1+e_2\sin\theta_1)\cos\theta_2+e_3\sin\theta_2)\cdots\cos\theta_{n-1}+e_n\sin\theta_{n-1})$$
$$F=\theta_1\frac{\partial{\bf x}}{\partial\theta_1}=\theta_1\,{\bf x}\cdot(e_1e_2)$$
We can eliminate the dependence on the coordinate system by noting that $e_1e_2=B$ could be any unit bivector ($B^2=-1$), and that $\theta_1$ is the angle of ${\bf x}$ in the $B$ plane:
$$\exp(\theta_1B)=e_1\frac{({\bf x}\cdot B)B^{-1}}{\lVert{\bf x}\cdot B\rVert}$$
I still don't know whether this can be used to find a more explicit formula for $|A|$...
Best Answer
This can be understood as follows. Consider the Jacobian matrix of the function $f$ at a point $p$ with $f(p) = c$. This is a linear approximation for $f$ near $p$, and takes the form of a $1 \times 3$ matrix transformation. Every vector in $\mathbb{R}^3$ in the null space of this matrix corresponds to a direction one can move away from $p$ on which $f$ is constant, thus a direction that lies on the set $\{f(x) = c\}$. If the linear transformation is surjective, the null space of the Jacobian is two-dimensional, meaning that the set $\{f(x) = c\}$ is two-dimensional near $p$. This provides the intuitive condition we need for the result to be true: the Jacobian should always be surjective, which when mapping to $\mathbb{R}^1$ just means that it is nonzero.