After changing default prefix I can use projectile commands using C-c p prefix.
When I press C-c p i see message C-c p is undefined in echo area, but prefix C-c C-p still works.
emacs -Q --load emacsprojectile.el(require 'package)
(let* ((no-ssl (and (memq system-type '(windows-nt ms-dos))
(not (gnutls-available-p))))
(url (concat (if no-ssl "http" "https") "://melpa.org/packages/")))
(add-to-list 'package-archives (cons "melpa" url) t))
(package-initialize)
(unless (package-installed-p 'projectile)
(package-install 'projectile))
(require 'projectile)
(projectile-mode +1)
(setq projectile-keymap-prefix (kbd "C-c p"))
Projectile version: 20180724.318
26.1
Linux 4.14.56 #2 SMP Wed Jul 18 00:09:15 CDT 2018 x86_64 Intel(R) Core(TM) i7-4790S CPU @ 3.20GHz GenuineIntel GNU/Linux

You have to set this before loading the mode. If for some reason this doesn't work as well - move the setq before the require.
It works if I set it before require statement. So in case of using use-package, should I set it in :init?
So in case of using use-package, should I set it in :init?
Yes, or :custom.
I checked and it works:
(use-package projectile
:init
(setq projectile-keymap-prefix (kbd "C-c p"))
:config
(projectile-mode +1))
Thanks, issue solved for me.
Most helpful comment
You have to set this before loading the mode. If for some reason this doesn't work as well - move the setq before the
require.