It is well known that General Relativity (GR) does not possess any non-trivial local (in a precise standard sense) and diffeomorphism invariant observables. We propose a generalized notion of local observables, which retain the most important properties that follow from the standard definition of locality, yet is flexible enough to admit a large class of diffeomorphism invariant observables in GR. The generalization comes at a small price, that the domain of definition of a generalized local observable may not cover the entire phase space of GR and two such observables may have distinct domains. However, the subset of metrics on which generalized local observables can be defined is in a sense generic (its open interior is non-empty in the Whitney strong topology). Moreover, generalized local gauge invariant observables are sufficient to separate diffeomorphism orbits on this admissible subset of the phase space. Connecting the construction with the notion of differential invariants, gives a general scheme for defining generalized local gauge invariant observables in arbitrary gauge theories, which happens to agree with well-known results for Maxwell and Yang-Mills theories. [arXiv:1503.03754]