Add locale, e.g. pl_PL.UTF-8, you don't have to set it as system default:
dpkg-reconfigure locales
Install PostgreSQL
apt-get update
apt-get install posgresql-9.4
Installation adds a cluster with default locale, recreate it with the correct one. The operation will destroy existing data in the cluster.