Run DELETE on each INSERT to enforce row limit
If you have an index on user_id, you can drop it and replace it with an index on (user_id,timestamp). This will also save a sort when displaying the latest log entries (WHERE user_id=... ORDER BY timestamp DESC LIMIT n).
Then:
SELECT timestamp FROM logs WHERE userid=1 ORDER BY timestamp DESC LIMIT 1 OFFSET 100

If there are more than 100 rows, this will return the timestamp of the 100th row. Otherwise it will return nothing. To delete the old logs for one user:
DELETE FROM logs WHERE userid=1 AND timestamp &lt;=
(SELECT timestamp FROM logs WHERE userid=1 ORDER BY timestamp DESC LIMIT 1 OFFSET 100);

This is a very fast query. If the select doesn't find any rows to delete, it will be well under 1ms.
To delete all the old logs:
DELETE FROM logs
USING (SELECT userid, f.timestamp FROM users CROSS JOIN LATERAL (SELECT timestamp FROM logs WHERE logs.userid=users.userid ORDER BY timestamp DESC LIMIT 1 OFFSET 100) f) oldlogs
WHERE logs.userid=oldlogs.userid AND logs.timestamp&lt;=oldlogs.timestamp;

This will probably seq-scan logs, so it could be slow. Here's a better one which will exploit the index on (userid,timestamp) and be fast if there is nothing to do:
DELETE FROM logs USING
( SELECT userid,timestamp FROM users 
  CROSS JOIN LATERAL (SELECT timestamp FROM logs WHERE logs.userid=users.userid ORDER BY timestamp DESC OFFSET 100) oldlogs ) o
WHERE logs.userid=o.userid AND logs.timestamp=o.timestamp;

To answer your comment &quot;what if many logs all have the same timestamp?&quot;... Well this should never happen since if you want your logs to be useful, they should be ordered by something unique, otherwise you don't know in what order they were logged. But... you can simply use the primary key:
-- one user
DELETE FROM logs USING
( SELECT id FROM logs WHERE logs.userid=123 ORDER BY timestamp DESC, id DESC OFFSET 100 ) o
WHERE logs.id=o.id;

-- all users
DELETE FROM logs USING
( SELECT oldlogs.id FROM users 
  CROSS JOIN LATERAL (SELECT id FROM logs WHERE logs.userid=users.userid ORDER BY timestamp DESC, id DESC OFFSET 100) oldlogs ) o
WHERE logs.id=o.id;

So if they have the same timestamp, the ORDER BY will keep the highest ids which should have been inserted last.