Ok I resolved this issue but was struggling for some time, so I don't know exactly what the easiest method is to do. But I will describe a recipe which will probably work for others as well.
The first important note is:
I think I resolved the issue since I can use the new upsert feature introduced in 9.5 (INSERT .. ON CONFLICT DO UPDATE ..). However my phpinfo() still reports version 9.3.
One more word about the problem situation: After adding the PostgreSQL repo and doing
apt-get upgrade I had two version of PostgreSQL apparently.
So to fix I did:
dpkg --get-selections | grep postgresql
You will get a list of all the related packages installed. I deinstalled them all with --purge (this will probably remove all your databases as well, no problem in my case since they were empty).
sudo apt-get remove --purge postgresql postgresql-9.5 postgresql-contrib etc.
It gave me errors on some packages but when I repeated it, in the end all packages were gone.
Also do this for the php pdo driver:
sudo apt-get remove --purge php5-pgsql
Now install postgresql again, only 9.5 will be installed.
sudo apt-get install postgresql postgresql-contrib php5-pgsql