You can just download the python script and install it somewhere, as described here:
https://git.wiki.kernel.org/index.php/GitP4#Adding_git-p4_to_an_existing_install
I found I had to put git-p4 into /usr/lib/git-core on my Ubuntu system for it to be invoked by git:
$ sudo mv /path/to/git-p4.py /usr/lib/git-core/git-p4
$ git p4 clone //depot/somebranch
(You need to remove the .py file extension).
Or you can just run it by hand (it's just a Python script and has no particular dependencies).
e.g.
$ /path/to/git-p4.py clone //depot/somebranch
The real problem is that the git-p4 Debian package has been removed because it depends on the non-free p4 client. See this bug report:
https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=715534
So creating a non-free or contrib git-p4 debian package would fix this properly.