A new formal scheme is presented in which Einstein's classical theory of General Relativity appears as the common, invariant sector of a one-parameter family of different theories. This is achieved by replacing the Poincaré group of the ordinary tetrad formalism with a q-deformed Poincare group, the usual theory being recovered at q = 1. Although written in terms of non-commuting vierbein and spin-connection fields, each theory has the same metric sector leading to the ordinary Einstein-Hilbert action and to the corresponding equations of motion. The Christoffel symbols and the components of the Riemann tensor are ordinary commuting numbers and have the usual form in terms of a metric tensor built as an appropriate bilinear in the vierbeins. Furthermore, we exhibit a one-parameter family of Hamiltonian formalisms for general relativity, by showing that a canonical formalism a la Ashtekar can be built for any value of q. The constraints are still polynomial, but the Poisson brackets are not skewsymmetric for q ≠ 1.