How to JOIN each row ON NOT IN ( SELECT ... )?
You can use not exists clause to do this.

SELECT
    u. ID AS user_id,
    s. ID AS song_id
FROM
    songs s,
    users u
WHERE
    NOT EXISTS (
        SELECT
            1
        FROM
            user_songs us
        WHERE
            us.user_id = u. ID
        AND us.song_id = s. ID
    )
ORDER BY
    1,
    2