For simple cases you do not even need a subquery.
If your secret first query only involves the same table:
DELETE FROM message m
WHERE  m.id = <something>
RETURNING m.*;          -- or what you need from the deleted row.
If your secret first query involves one or more additional tables:
DELETE FROM message m
USING  some_tbl s
WHERE  s.some_column = <something>
AND    m.id = s.id
RETURNING m.id, s.foo;  -- you didn't define ...
Solution for actual query (after comments)
An educated guess, to delete the oldest row (smallest timestamp) from each set with identical id:
DELETE FROM message m
USING (
   SELECT DISTINCT ON (id)
          id, timestamp
   FROM   message
   WHERE  queue_id = _queue_id
   AND    source_client_id = _source_client_id
   AND   (target_client_id IN (-1, _client_id))
   ORDER  BY id, timestamp
   ) sub
WHERE m.id = sub.id
AND   m.timestamp = sub.timestamp
RETURNING m.content
INTO  rv;
Or, if (id, timestamp) is UNIQUE, NOT EXISTS is probably faster:
DELETE FROM message m
WHERE  queue_id = _queue_id
AND    source_client_id = _source_client_id
AND    target_client_id IN (-1, _client_id)
AND    NOT EXISTS (
   SELECT 1
   FROM   message
   WHERE  queue_id = _queue_id
   AND    source_client_id = _source_client_id
   AND    target_client_id IN (-1, _client_id)
   AND    id = m.id
   AND    timestamp < m.timestamp
   ) sub
WHERE  m.id = sub.id
RETURNING m.content
INTO   rv;
More about DISTINCT ON and selecting "the greatest" from each group:
If performance is your paramount objective, look to the last chapter ...
Aside: timestamp is a basic type name in Postgres and a reserved word in standard SQL. Don't use it as identifier.
Solution in comment below, audited:
DELETE FROM message m
USING (
   SELECT id
   FROM   message
   WHERE  queue_id = _queue_id
   AND    target_client_id IN (client_id, -1)
   ORDER  BY timestamp
   LIMIT  1
   ) AS tmp
WHERE  m.id = tmp.id
RETURNING m.content
INTO rv;
INTO ... only makes sense inside a plpgsql function, of course.
An index on (queue_id, timestamp) makes this fast - possibly even a partial index with the condition WHERE target_client_id IN (client_id, -1) (depends).