Como encontrar o registro anterior [n-per-group max(timestamp) <timestamp]?

A última abordagem com variáveis é razoável. Você também pode tentar:

SELECT collect.*,
       (select max(timestamp)
        from data
        where data.channel_id = collect.channel_id AND data.timestamp < collect.timestamp
       ) AS prev_timestamp
FROM data AS collect 
WHERE collect.channel_id = 14 AND collect.timestamp >= 0 
ORDER BY collect.timestamp;

Além disso, crie índices em:collect(channel_id, timestamp).

EDITAR:

O seguinte pode ser o mais rápido:

  select d.*,
         if(@channel_id = channel_id, @prev_timestamp, NULL) as prev_timestamp,
         @channel_id := channel_id, @prev_timestamp = timestamp
  from data d cross join
       (select @channel_id := 0, @prev_timestamp := 0) vars
  where collect.channel_id = 14 AND collect.timestamp >= 0 
  order by channel_id, timestamp;