#Pyth, 20 bytes

Jt^2hslhQ#p/=%QJ=/J2

Runs in O(log(input())), well under a second for the final test case. Based around a run until error loop. No trailing newline.

Demonstration.

Explanation:

Jt^2hslhQ#p/=%QJ=/J2
 Implicit: Q is the input.
 lhQ log(Q+1,2)
 slhQ floor(log(Q+1,2))
 hslhQ floor(log(Q+1,2))+1
 ^2hslhQ 2^(floor(log(Q+1,2))+1)
 t^2hslhQ 2^(floor(log(Q+1,2))+1)-1
Jt^2hslhQ J=2^(floor(log(Q+1,2))+1)-1
 # until an error is thrown:
 =%QJ Q=Q%J
 =/J2 J=J/2
 / The value Q/J, with the new values of Q and J.
 p print that charcter, with no trailing newline.

J is initialized to the value of the smallest skew binary digit position that is larger than the input. Then, each time through the loop, we do the following:

• Remove each digit of value J from Q with =%QJ. For instance, if Q=10 and J=7, Q becomes 3, which corresponds to the skew binary changing from 110 to 10. This has no effect in the first iteration.
• Change J to the next smaller skew binary base value with =/J2. This is floored division by 2, changing J=7 to J=3, for instance. Because this happens before the first digit is output, J is intialized one digit position higher than needed.
• Find the actual digit value with /QJ (effectively).
• Print that value with p, instead of Pyth`s default printing, to avoid the trailing newline.

This loop will repeat until J becomes zero, at which point a divide by zero error will be thrown, and the loop will end.

Pyth, 20 bytes

Jt^2hslhQ#p/=%QJ=/J2

Runs in O(log(input())), well under a second for the final test case. Based around a run until error loop. No trailing newline.

Demonstration.

Explanation:

Jt^2hslhQ#p/=%QJ=/J2
 Implicit: Q is the input.
 lhQ log(Q+1,2)
 slhQ floor(log(Q+1,2))
 hslhQ floor(log(Q+1,2))+1
 ^2hslhQ 2^(floor(log(Q+1,2))+1)
 t^2hslhQ 2^(floor(log(Q+1,2))+1)-1
Jt^2hslhQ J=2^(floor(log(Q+1,2))+1)-1
 # until an error is thrown:
 =%QJ Q=Q%J
 =/J2 J=J/2
 / The value Q/J, with the new values of Q and J.
 p print that charcter, with no trailing newline.

J is initialized to the value of the smallest skew binary digit position that is larger than the input. Then, each time through the loop, we do the following:

• Remove each digit of value J from Q with =%QJ. For instance, if Q=10 and J=7, Q becomes 3, which corresponds to the skew binary changing from 110 to 10. This has no effect in the first iteration.
• Change J to the next smaller skew binary base value with =/J2. This is floored division by 2, changing J=7 to J=3, for instance. Because this happens before the first digit is output, J is intialized one digit position higher than needed.
• Find the actual digit value with /QJ (effectively).
• Print that value with p, instead of Pyth`s default printing, to avoid the trailing newline.

This loop will repeat until J becomes zero, at which point a divide by zero error will be thrown, and the loop will end.

Pyth, 17 bytes

Ljb3ye.f!-P-yZ01Q

This is shorter, but ridiculously slow - O(output^log_2(3)). Some ideas taken from @Dennis's answer, here .

Demonstration.

This is shorter, but ridiculously slow - O(input()^2). Also, I hesitate to post it, since it's arguably just a port of @Dennis's CJam answer.

This is shorter, but ridiculously slow - O(output^log_2(3)). Some ideas taken from @Dennis's answer, here.

Demonstration.