Generate a random combination in O(k) time and space?
Suppose that $k \leq n/2$ (the constant $1/2$ is arbitrary) – otherwise you can just use the $O(k)$ time, $O(n)$ space algorithm, which is the second algorithm that you mention.

One way of solving your problem is as follows:


Start with the empty list.
Repeat $k$ times:


Generate a random number from $1$ to $n$.
Check if it is already in the list.
If so, go back to step 1.
Otherwise, add it to the list.



The expected number of steps in this algorithm is
$$
\frac{1}{1-0/n} + \frac{1}{1-1/n} + \cdots + \frac{1}{1-k/n} = n \left(\frac{1}{n} + \cdots + \frac{1}{n-k}\right) \leq \frac{k}{2},
$$
since $k \leq n/2$.

Using a hash table, use should be able to implement step 2 in $O(1)$ expected time and $O(k)$ space.