Building ideal skip lists
Following your idea, you can do this:


Iterate through the (sorted) list.
For every item, flip a coin until you get a $0$. The item's level is the number of $1$s you got; create the tower of pointers and link already created towers accordingly.


For every item, the expected level is $\frac{1}{p}$ with $p$ the probability of a $1$ (geometric distribution); therefore, every item causes constant runtime in expectation, resulting in a total expected runtime in $O(n)$ for creating the list. As the maximum level is $\log_{1/p} n$ in expectation and you only need to remember the last (dangling) pointer for every level, the algorithm requires only $O(\log_{1/p} n)$ additional memory in expectation.

Note that the resulting list is not stricly "ideal" but in expectation; the interesting operations have logarithmic expected runtime due to the resulting distribution. See William Pugh's Skip Lists: A Probabilistic Alternative to Balanced Trees (1990) and the work referenced there for details.

It is clear that there can be no algorithm that works in expected time $o(n)$; in expectation, there have to be $\frac{n}{2}$ items on level two so at least that many have to be investigated (in expectation).