Parton distributions with theory uncertainties: general formalism and first phenomenological studies