What linked list data structure adjustments would give me fast random lookup?
One simple approach might be to use a doubly-linked list of extents, where each extent represents a sequence of contiguous records.  The records within each extent could in turn be represented with a doubly linked list.

This preserves your ability to do $O(1)$ time splicing, and now the insert operation takes $O(k)$ time, where $k$ is the number of extents (rather than $O(n)$, where $n$ is the number of records).  If you have many fewer extents than records, this might be a partial improvement.

I don't know whether this will be better than a simple skip list or binary tree.

Note that if you use a binary tree, you can still do efficient splicing.  The splicing operation is no longer $O(1)$ time, but it can be done in $O(\log \ell)$ time, where $\ell$ is the number of records in the spliced segment.  This is not as fast as $O(1)$ time splicing, but depending upon the relative frequency of your different operations, it is another data structure you could consider (e.g., benchmark on realistic data sets).

And, of course, you could combine these ideas, e.g., with a binary tree of extents, where each extent is in turn a doubly-linked list of contiguous records.  Inserts will take $O(\lg k)$ time, and splicing can be done in $O(\lg \ell)$ time (both of which might potentially be better than the $O(\lg n)$ achieved through a simple binary tree).