Assuming you run another statements before calling new_customer, and those acquire a lock that conflicts with EXCLUSIVEEXCLUSIVE (basically, any data modification in the customer table), the explanation is very simple.
One can reproduce the problem with a simple example (not even including a function):
CREATE TABLE test(id INTEGER);
1st session:
BEGIN;
INSERT INTO test VALUES(1);
2nd session
BEGIN;
INSERT INTO test VALUES(1);
LOCK TABLE test IN EXCLUSIVE MODE;
1st session
LOCK TABLE test IN EXCLUSIVE MODE;
When the first session does the insert, it acquires the ROW EXCLUSIVEROW EXCLUSIVE lock on a table. Meanwhile, session 2 tries also gets the ROW EXCLUSIVEROW EXCLUSIVE lock, and tries to acquire an EXCLUSIVEEXCLUSIVE lock, at. At which point it has to wait for the 1st session, since EXCLUSIVEEXCLUSIVE lock conflicts with ROW EXCLUSIVEROW EXCLUSIVE. At last, 1st session jumps the sharks and tries to get an EXCLUSIVE LOCKEXCLUSIVE lock, but since the locks are acquired in order, it queues after the 2nd session, which. This, in orderturn, waits for the 1st one, producing a deadlock:
DETAIL: Process 28514 waits for ExclusiveLock on relation 58331454 of database 44697822; blocked by process 28084. Process 28084 waits for ExclusiveLock on relation 58331454 of database 44697822; blocked by process 28514.
DETAIL: Process 28514 waits for ExclusiveLock on relation 58331454 of database 44697822; blocked by process 28084.
Process 28084 waits for ExclusiveLock on relation 58331454 of database 44697822; blocked by process 28514
The solution to this problem is to acquire locks as early as possible, usually as a first thing in a transaction. On the other hand, PostgreSQL workload only needs locks in some very rare cases, so I'd suggest rethinking the way you do the upsert (take a look at this article http://www.depesz.com/2012/06/10/why-is-upsert-so-complicated/).
