I finally got a successful workaround for this problem.

I was facing this problem probably since emacs 24.3 and also on 24.4 and
the master head builds from emacs git for version 25.0.50.0.

I was getting "*ERROR*: Invalid face: linum" when trying to start emacs
with "emacsclient -a '' -c" with my init.el having "(require 'nlinum)".

Workaround:

(if (daemonp)
    (add-hook 'window-setup-hook
              (lambda ()
                (message ">> Daemon mode")
                 ;; It is mandatory to load linum AFTER the frames are set
up
                 ;; Else, I get "*ERROR*: Invalid face: linum"
                 (require 'nlinum)))
  (progn
    (message ">> Non daemon mode")
    (require 'nlinum)))

Actual snippet in my init.el:
https://github.com/kaushalmodi/.emacs.d/blob/a0955aeead27bf6ccdb0219edfbfade10a823728/init.el#L220-228