Will (ROWLOCK,UPDLOCK,READPAST) with ORDER BY non-clustered columns work?
I would opt for marking the row as "in process" (e.g. having a status for the equivalent of "checked out") as opposed to relying solely on row locking:

;WITH x AS 
(
  SELECT TOP (1) i_task_id, i_status
    FROM dbo.TAB WITH (ROWLOCK,UPDLOCK,READPAST)
    WHERE i_status = 1
    ORDER BY i_priority DESC,i_task_id ASC
)
UPDATE x SET i_status = 2 -- in process? locked?
  OUTPUT inserted.i_task_id
  WHERE i_status = 1;


No blocking or deadlocking in my tests. The 6th session won't block or deadlock either, it will just return no rows.