Before describing my construction, I will explain why it is natural: In Gil's setup, we are supposed to fix a certain set of vertices (points in some space $X$) and vary edges connecting them. If edges are geodesics, we then need $X$ where geodesics with fixed end-points are far from being unique. Round $n$-spheres $S^n$ provide natural examples, where antipodal points are connected by $n-1$ dimensional families of geodesics. However, in the sphere, every point is antipodal to a unique point, so $S^n$ is not good enough. Spherical buildings are a natural generalizations of round spheres where antipodes are not unique.
Here is a general recipe for getting spaces of $d$-dimensional space of geodesics connecting "antipodal" points.
Let $G$ be a real Lie group which is the set of real points of an algebraic semi-simple group over reals (I assume that $G$ has no compact factors). I will assume that $r$, the (real) rank of $G$, is $>1$. Let $R$ be the root system of $G$ and $R_+$ be the set of positive roots with respect to a choice of Borel subgroup $B\subset G$. Let $W$ be the Weyl group of $G$.
One then associates with $G$ a spherical (Tits) building $X$. One can think of $X$ combinatorially as a cell complex encoding inclusions between parabolic subgroups of $G$. I will think of $X$ as a metrized cell complex, where each cell is isometric to a cell in the Coxeter complex $(S,W)$, here $S$ is the sphere of dimension $r-1$. Given such metric, one can talk about geodesic segments in $X$, which are (globally) length-minimizing paths.
The group $G$ acts on $X$ by isometries, preserving the combinatorial structure of $X$. Then every geodesic in $X$ has length $\le \pi$ and is contained in an apartment in $X$, which is an isometrically embedded copy of $S$ in $X$. Chambers in $X$ are the facets, they are stabilized by the Borel subgroups of $G$.
More generally, stabilizers $G_\sigma$ of cells $\sigma$ in $X$ are parabolic subgroups in $G$ (by the definition of $X$). I will use the notation $G_x$ for the $G$-stabilizer of a point $x$ in $X$. Then $G_x=G_\sigma$, where $\sigma\subset X$ is the smallest cel containing $x$. Two oriented geodesics are called congruent if there exists an orientation-preserving isometry between them induced by an element of $G$. Then, given an oriented geodesic $\gamma\subset X$, the space of $\Gamma_\gamma$ of oriented geodesics in $X$ congruent to $\gamma$ identifies naturally with $G/G_\Gamma$, where $G_\gamma$ is the stabilizer of $\gamma$ in $G$. It is easy to see that $G_\gamma$ is again an algebraic subgroup of $G$, so $\Gamma_\gamma$ is a homogeneous manifold. This explains why sets of congruent geodesics are useful for defining "edges'' between points in $X$.
Two points in $X$ are called antipodal if they are within distance $\pi$. The key property of $X$ is that it has abundance of antipodal points and geodesics between such points are far from being unique. First of all, if $x, y$ are antipodal and belong to an apartment $S\subset X$ then we have $r-2$-dimensional space of geodesics between $x$ and $y$ contained in $S$. However, most of these will not be congruent to each other. More interesting construction of geodesics connecting $x$ to $y$ is as follows: Let $\xi$ be a germ of a geodesic in $X$ emanating from $x$. Then $\xi$ can be extended (uniquely) to a geodesic $\gamma_\xi$ connecting $x$ to $y$. One obtains congruent geodesics $\gamma_\xi$ by using germs $\xi$ which belong to a single $G_x$-orbit, where $G_x=G_\sigma$ is a parabolic subgroup of $G$ ($\sigma$ is the minimal cell in $X$ containing $x$).
Thus, the space of congruent geodesics connecting $x$ to $y$ (with germs at $x$ of type $\xi$) is naturally identified with the quotient
$$
G_x/G_\xi=G_\sigma/G_\tau,
$$
where $\tau$ is the smallest cell in $X$ containing $\xi$.
Our goal is then to find buildings $X$ and pairs of cells $(\sigma, \tau)$, with $\sigma\subset \tau$, so that:
$dim(G_\sigma/G_\tau)=4$.
The Levi subgroup of $G_\sigma$ admits an epimorphism to a group locally isomorphic to $SL(2, {\mathbb R})$ so that $G_\tau$ is contained in the kernel.
I will do so when $G$ is split, since computations are easier in this case. Then each parabolic subgroup $P$ of $G$ corresponds (up to conjugation) to a root subsystem $R'$ in $R$, where ${R}'$ is obtained by omitting some nodes in the Dynkin diagram of $R$.
Then $P$ has dimension
$$|R_+'| + |R_+| + r$$
Note that $|R_+| + r$ is the dimension of the Borel subgroup $B$ of $G$, the smallest possible dimension for a parabolic. In particular,
$$
d(R')=dim(P)-dim(B)= |{R'}_+|.
$$
Thus, if we take, say, $G_\tau=B$, then I can get any value for
$$
d(R')=dim(P)-dim(B)=dim(G_\sigma/G_\tau)
$$
(not exceeding, say, $r/2$) by taking $R'$ to be a direct sum of rank 1 root subsystems in $R$ (so that Dynkin diagram for $R'$ contains no edges). This will satisfy condition 1, of course.
Here is a bit more interesting example. Let $G=SL(5, {\mathbb R})$, $r=4$. Take $R'$ obtained by removing the one of the middle nodes from Dynkin diagram of $R$ so that $R'\cong A_1\oplus A_2$ and the Levi factor of $P$ is locally isomorphic to $SL(2, {\mathbb R})\times SL(3, {\mathbb R})$. Then $d(R')=1+3=4$. In particular, $P$ is a maximal parabolic and, hence, $\sigma=x$ is a vertex of $X$. Alternatively, one can use $G=SL(3, {\mathbb R})\times SL(3, {\mathbb R})$, where it does not matter which node you remove, you still get $R'\cong A_1\oplus A_2$. Below, I will consider $G= SL(5, {\mathbb R})$.
Now, the space of geodesics $\Sigma_{x,y,\xi}$ connecting $x$ to an antipodal point $y$ and having a fixed regular congruence type, is a smooth 4-dimensional manifold. (Regular congruence type corresponds to the assumption that the germ $\xi$ is not contained in any wall of $X$, so $\tau$ is a chamber in $X$ and $G_\tau$ is Borel.) This is the degree of freedom for edges in $X$ that Gil asked for.
Now, I can explain why the condition 1 above is useful. Suppose that $H$ is a group which
admits an epimorphism $\rho: H\to SL(2, {\mathbb R})$. Then $H$ contains a codimension 1 subgroup $H'$ obtained as the preimage of a Borel in $SL(2, {\mathbb R})$. In the context of the pair $P=G_\sigma, G_\tau$, I get another parabolic $P'=H'$ of codimension 1 in $P=H$ and containing $G_\tau$. Now, using $P'$-orbit of the above germ $\xi$ (instead of the $P$-orbit), I will get a 3-dimension submanifold in the manifold of geodesics $\Sigma_{x,y,\xi}$.
Thus, we got spaces of edges connecting $x$ to $y$ which have dimensions $4$ and $3$ respectively, which is what Gil asked for.
Our next goal is to impose restrictions on 2-faces of the 3-sphere, i.e., triangles $T_i$ whose vertices are antipodal vertices $x_1, x_2, x_3$ in $X$ and whose edges are described above. Let $\xi_i, i=1,2,3$ denote the germs (at $x_i$) of the oriented edges $[x_i,x_{i+1}]$, each germ $\xi_i$ is contained in a unique chamber $\sigma_i$ in $X$. Generically, the chambers $\sigma_i$ are mutually antipodal. Let $C_3(X)$ denote the space of ordered triples of pairwise antipodal chambers in $X$. This space is birational to $U/T$, where $U$ is unipotent radical of $B$ and $T\subset G$ is maximal torus normalizing $U$ and acting on $U$ via conjugation. Hence, $C_3(X)$ has dimension $|R_+|-r$, in our example $G=SL(5, {\mathbb R})$, it is $10-4=6$.
Thus, we have plenty of functions on $C_3(X)$ to choose from in order to impose one restriction for each triangle. Below is a somewhat random choice, based on my reading of the paper by Fock and Goncharov "Moduli spaces of local systems and higher Teichmuller theory". A chamber in $X$ (in the case of $G=GL(n, {\mathbb R})$ is given by a complete flag $F=(V_0\subset V_1\subset ... \subset V_n)$ in $V={\mathbb R}^n$. If $n=3$, then $C_3(X)$ is 1-dimensional with a single (most natural) invariant of a a triple of flags $(F_1,F_2,F_3)$ given by Goncharov's triple ratio,
$$
\rho(F_1,F_2,F_3)=\frac{\langle f_1, v_2 \rangle \langle f_2, v_3 \rangle \langle f_3, v_1 \rangle}
{\langle f_1, v_3 \rangle \langle f_2, v_1 \rangle \langle f_3, v_2 \rangle}
$$
Here $f_k$'s are linear functions on ${\mathbb R}^3$ whose kernels are 2-planes in the flags $F_k$ and $v_k$'s are basis vectors in the lines in the flags $F_k$.
For $n\ge 4$, given a triple of flags $(F_1,F_2,F_3)$, taking quotient of $V$ by the subspace $V_{n-3}$ appearing in the $i$-th flag, I reduce the dimension to $3$ and, hence, can get the triple ratio $\rho_i$ of the image of my flag in the resulting 3-dimensional space. Now, I will take function $h: C_3(X)\to {\mathbb R}$ given by
$$
h(F_1,F_2,F_3)=\rho^2_1+\rho^2_2+\rho^2_3.
$$
Then, I impose one restriction $h(T_i)=t_i\in {\mathbb R}_+$ for each triangular face $T_i$ in the 3-sphere. This works for general $n$, but I will restrict to the case $n=5$.
At the moment, I have no idea where the symplectic structure on the resulting space of maps of $S^3$ to $X$ would come from (actually, I do, I just do not know how to make it work). Instead of $G=SL(5, {\mathbb R})$ one may have to use another Lie group. The easiest way to get a symplectic structure is to use some form of symplectic reduction, which is how it was done first by Klyachko and then in my paper with Millson "The symplectic geometry of polygons in Euclidean space", Journal of Diff. Geometry, Vol. 44 (1996) p. 479-513,
or in my paper with Millson and Treloar "The symplectic geometry of polygons in hyperbolic 3-space", Asian Journal of Math., Vol. 4 (2000), N1, p. 123-164. The latter used Poisson Lie theory, which, somehow, looks more promising.
Best Answer
Q3: Laman's theorem is the same on the sphere.
Indeed, a configuration with $n$ vertices and $m$ edges is defined by a system of $m$ equations in $2n-3$ variables (there are $2n$ coordinates of points, but we may assume that the first point is fixed and the direction of one of the edges from the first point is fixed too). The the left-hand sides are analytic functions of our variables and the right-hand sides are the squares of the lengths of the bars (on the sphere, cosines rather than squares).
Consider this system as a map $f:\mathbb R^{2n-3}\to\mathbb R^m$. The rigidity means that a generic point $x\in\mathbb R^{2n-3}$ cannot be moved within the pre-image of $f(x)$. This implies that $rank(df)=2n-3$ on an open dense set. Choose a configuration from this set and project it to the sphere of radius $R\to\infty$. The equations on the sphere converge to those in the plane, hence the rank of the linearization on the sphere will be maximal ($=2n-3$) for all large $R$. So we get an open set of configuration on the sphere where the linearization has the maximal rank (and this implies rigidity). Since all functions involved are analytic and the rank is maximal on an open set, it is maximal generically. So our linkage is generically rigid on the sphere.
Conversely, consider a flexible linkage on the plane. If $m<2n-3$, it will be flexible on the sphere by a dimension counting argument. Otherwise, by Laman's theorem, there is a subgraph with $r$ vertices and more than $2r-3$ edges. Consider such a subgraph for which $r$ is minimal. Then, by Laman's theorem, we can remove some edges so that this subgraph remains rigid. And, by the above argument, it is rigid on the sphere too. So the edges that we removed were redundant both in the plane and in the sphere. Let's forget about them and repeat the procedure. Eventually we will get a linkage with fewer than $2n-3$ edges.