How to prevent deadlocks in many-to-many insert/update trigger function?
This might require careful examination, knowledge of the complete situation and more time than I can spend now. Or maybe I am missing something obvious. Whatever else might go wrong here, some things stand out:


Remove the FOR UPDATE SKIP LOCKED completely. It makes no sense where you use it. While selecting from the CTE, which holds rows with exclusive lock already, that makes no sense. It also would not make sense to skip any rows at this stage of the query.
COST 1 is misleading. The default is COST 100 and your trigger function is more in the realm of COST 5000. Leave the default or set it higher. Probably unrelated to the deadlock.
An AFTER trigger might be more susceptible to deadlocks than rewriting the whole workflow with a single query (with multiple data-modifying CTEs).
My shot in the dark: the deadlock is caused by the FK constraint trying to take a ShareLock on url_starting while concurent transactions try to modify the same row after having taken a similar ShareLock themselves and vice versa. A quick and dirty solution might be to drop the FK constraint tweet_x_url_starting if you can afford that. You could at least try that to verify it's part of the problem.


If you want to continue your learning spree - here is one more that seems relevant:


How to use RETURNING with ON CONFLICT in PostgreSQL?