Random number generator that returns unique entries in sorted order

I need a generator for many (up to one trillion, 10^12) unique random 64-bit numbers. The generator needs to return the numbers in sorted order (Long.MIN_VALUE to Long.MAX_VALUE). The problem is that sorting $10^{12}$ numbers is slow. The use case is replicating a test that was run for BBHash (in the paper, 4.5 Indexing a trillion keys).

The straightforward solution is to create a set in memory, using a huge bit set or so to ensure no duplicates are returned. But that uses too much memory or I/O. I'd like to use at most a few MB of internal state.

The generator should use a java.util.Random internally. It should be as "fair" as possible (have the same statistical distribution as if generated otherwise). I would also like to have a version for 128-bit numbers (2 longs).

What I have so far is code to create a set in memory (Java code):

public static void main(String... args) {
    for(long x : randomSet(10, 0)) {
        System.out.println(x);
    }
}

static Iterable<Long> randomSet(int size, int seed) {
    Random r = new Random(seed);
    TreeSet<Long> set = new TreeSet<Long>();
    while (set.size() < size) {
        set.add(r.nextLong());
    }
    return set;
}

-8292973307042192125
-7423979211207825555
-6688467811848818630
-4962768465676381896
-2228689144322150137
-1083761183081836303
-279624296851435688
4437113781045784766
6146794652083548235
7105486291024734541

The simplest (wrong) solution, which is not random, is to distribute the results evenly. I don't think a solution along the line of "add a random gap" will work, because it is slow, and the sum of such gaps, after 10^12, will not land where it should (well, maybe: remember how many numbers are left, then re-calculate the distribution...). I think the following should work, but is complex, and not sure what formulas to use: for each bit level, recursively, calculating how many 0s / 1s will likely occur (using the Binomial distribution or the approximation, the normal / Gaussian distribution, somehow). Stop at some point (say, blocks of 1 million entries or less), use the code above, for speed. But maybe there is an elegant solution. Maybe this is related to the Metropolis–Hastings algorithm, not sure. I read "An Efficient Algorithm for Sequential Random Sampling", but I think it is only for small n, and I find it hard to get to a simple algorithm from this.

Java code would be best, but C is fine (anyway at some point I might have to convert it to C / C++). I would like to not use too many libraries, to simplify porting.