Simultaneous calls to the same function: how are deadlocks occurring?
I posted this to pgsql-bugs and the reply there from Tom Lane indicates this is a lock escalation issue, disguised by the mechanics of the way SQL language functions are processed. Essentially, the lock generated by the insert is obtained before the exclusive lock on the table:


  I believe the issue with this is that a SQL function will do parsing (and
  maybe planning too; don't feel like checking the code right now) for the
  entire function body at once.  This means that due to the INSERT command
  you acquire RowExclusiveLock on the "test" table during function body
  parsing, before the LOCK command actually executes.  So the LOCK
  represents a lock escalation attempt, and deadlocks are to be expected.
  
  This coding technique would be safe in plpgsql, but not in a SQL-language
  function.
  
  There have been discussions of reimplementing SQL-language functions so
  that parsing occurs one statement at a time, but don't hold your breath
  about something happening in that direction; it doesn't seem to be a
  high priority concern for anybody.
  
  regards, tom lane


This also explains why locking the table outside the function in a wrapping plpgsql block (as suggested by @ypercube) prevents the deadlocks.