I'll repost my (OP) case, for the references to it to make more sense to the others.
Having the following table:
CREATE TABLE "song_artist" (
"song_id" INT8 NOT NULL,
"artist_id" INT8 NOT NULL,
PRIMARY KEY ("song_id", "artist_id")
);
Even trying to protect from this with a select, won't help to get away from
the error, because at the beginning of the transaction the key does not
exist yet.
BEGIN ISOLATION LEVEL SERIALIZABLE READ WRITE;
INSERT INTO song_artist (song_id, artist_id)
SELECT 1, 2
WHERE NOT EXISTS (SELECT * FROM song_artist WHERE song_id=1 AND
artist_id=2);
COMMIT;