A relativistic density-functional theory based on a Fock-space effective quantum-electrodynamics (QED) Hamiltonian using the Coulomb or Coulomb-Breit two-particle interaction is developed. This effective QED theory properly includes the effects of vacuum polarization through the creation of electron-positron pairs but does not include explicitly the photon degrees of freedom. It is thus a more tractable alternative to full QED for atomic and molecular calculations. Using the constrained-search formalism, a Kohn-Sham scheme is formulated in a quite similar way to non-relativistic density-functional theory, and some exact properties of the involved density functionals are studied, namely charge-conjugation symmetry and uniform coordinate scaling. The usual no-pair Kohn-Sham scheme is obtained as a well-defined approximation to this relativistic density-functional theory.