In fact, the concept of "freestanding implementation" (as opposed to "hosted implementation", which is a implementation of the full standard) exists in C, and is sometimes used in embedded systems:

  a conforming freestanding implementation is only required
  to provide certain library facilities: those in <float.h>,
  <limits.h>, <stdarg.h>, and <stddef.h>; since AMD1, also
  those in <iso646.h>; since C99, also those in <stdbool.h>
  and <stdint.h>; and since C11, also those in <stdalign.h>
  and <stdnoreturn.h>

(source: http://gcc.gnu.org/onlinedocs/gcc-4.7.1/gcc/Standards.html)

So yes, a conforming (freestanding) C implementation without printf for embedded systems can exist.