Uiua, 36 bytes

do(swfor&pjoigibelbacmemflo%rnd1)1[]

the same code formatted (20 chars, 42 bytes in utf-8):

⍢(⨬⊃&p⊂⋅∘◡˜∊⌊÷⚂1)1[]

Japt, 12 bytes

I think this is valid, based on what other solutions are doing.

@øX}f@1/Mr)f

Try it

20 bytes

If not, this version ouputs infinitely.

ß[ON]mp@NøX}f@1/Mr)f

Try it

Raku (Perl 6) (rakudo), 24 bytes

say (^2e9).pick for ^2e9

Attempt This Online!

So, technically this will work, but the pick method has to load all two billion numbers into memory before it can get working. You can test it with a smaller number:

say (^2e5).pick for ^2e5

I tried it with ∞ but Raku didn't like that.

AWK, 62 bytes

{for(;x=rand()*$1;printf!b[a=int(x)]++?a"\n":X)gsub(/\./,X,x)}

Attempt This Online!

{for(;x=rand()  # infinite loop
*$1;            # seed from input
printf          # format print
!b[a=int(x)     # remove leading zeros
]++             # have we seen it before
?a"\n":X)       # output
gsub(/\./,X,x)} # strips dot

APL, 33 bytes

∇P
S←⍬
→2/⍨S∊⍨X←⌊÷1-?0
S,←⎕←X
→2∇

JavaScript REPL, 48 bytes

for(o=[];;)o[n=1/Math.random()|0]||alert(o[n]=n)

JavaScript ES6, repeating call, 50 Bytes

c={0:9};f=_=>c[~~_]|Math.random()<.9?f(-~_):c[_]=_

Clojure, 100 bytes

(fn[](let[a(atom[])](filter #(if-not(some #{%}@a)(swap! a conj %))(repeatedly #(bigint(/(rand)))))))

This function returns an infinite sequence of integers. To get the nth number of this series:

(nth (fn[]...) n)

To get the first n terms of this series:

(take n (fn[]...))

EDIT: Golfed 11 bytes (Thanks @NikoNyrh!) and added 3 bytes (changed int to bigint, to improve accuracy).

Clojure, 112 (or 119) 114 bytes

Update, uses 1 / (rand) to get an "infinite" range of bigints:

#(filter pos?(map first(reductions(fn[[v p]r](if(p r)[0 p][r(conj p r)]))[0#{}](for[i(range)](bigint(/(rand)))))))

Original:

#(filter pos?(map first(reductions(fn[[v p]r](if(p r)[0 p][r(conj p r)]))[0 #{}](for[i(range)](rand-int 2e9)))))

I'm hoping to see an alternative approach. Anyway, this will generate integers between 1 and 2e9, Java's integers are signed to the "real" maximum is 2147483647, which is 7 bytes longer expression (Integer/MAX_VALUE is even longer). 0 is used as an indication of a duplicate values and are filtered from the output sequence.

Haskell, 60 59 56 bytes

((a:b)#h)(n:r)|n=a:((h++b)#[])r|q<-a:h=(b#q)r
[1..]#[]

Takes the seed as an infinite list of Bool.

Usage example: ([1..]#[]) [True,False,False,True,True,False,True,True,False,True,False,True,True,False,False,False,False,False,False,True....] -> [1,4,3,5,2,7,8,6,15,...].

Try it online!

Start with the list [1..]. If the next element from the seed is False, skip the next element of the list. If it's a True, output the current element, remove it from the list and start from the beginning. h keeps track of the skipped elements and is prepended (-> h++b) to the list of available numbers in the True case.

Java 8, 136 bytes

import java.util.*;()->{Set s=new HashSet();for(int n;;s.add(n))System.out.print(!s.contains(n=new Random().nextInt(-1>>>1))?n+";":"");}

Explanation:

Try it here. (Wait 60 seconds for the TIO to time-out to see the result.)

import java.util.*;     // Required import for the Set, HashSet, and Random

()->{                   // Method without parameters nor return-type
  Set s=new HashSet();  //  Set to keep track of numbers we've already outputted
 for(int n;;            //  Loop infinitely
     s.add(n))          //   And every time we output a random number, add it to the Set
   System.out.print(    //   Output:
    !s.contains(        //    If we haven't outputted it yet:
     n=new Random().nextInt(-1>>>1))?n+";"
                        //     A random number (range of int: 0 - 2³²)
    :                   //    Else:
     "");               //     Output nothing
}                       // End of method

Bash, 23 bytes

yes \ |nl|xargs shuf -e

Try it online!

yes \ prints infinite spaces, nl numbers lines, suff -e shuffless lines without repetition.

Python 2, 93 87 bytes

-3 bytes thanks to Uriel (move r=1 to beginning of the loop to avoid initialisation)

from random import*
a=[]
while 1:
 r=1
 while r in a or.5<random():r+=1
 a+=[r];print r

Try it online!

Keeps adding one while the number is either unavailable or a coin flip comes up heads.
Low numbers have much more probabilistic weight than high numbers.

Aceto, 29 21 bytes

Writing to STDOUT, with a consistent, unambiguous separator between integers (such as a newline), with output prior to termination of the program

p<LL
 v`O
I?<\
0MLCnO

1. Push a zero, increment it and go in a random direction. Two of the directions lead back to the random direction field, one leads back to incrementation (so it is incremented a random amount of times).
2. When the fourth choice is made, we memorize and immediately load the value, then check whether it's contained in the stack already. If so, we jump to the origin and try again.
3. Otherwise, we load the value twice (once for printing, once for storage), print it and a newline and go back to the origin.

Massively favours low numbers, but there is a small chance for it to print any number at any point.

Mathematica, 83 bytes

s=5;l={};t=1;While[t<30,If[l~FreeQ~s,Print@s];l~AppendTo~s;s=RandomInteger@100;t++]

starting with 5

Try it online!

MATL, 10 bytes

`x1r/XktGm

Try it online!

Explanation

A candidate output, say n, is generated as ceil(1/r), where r is uniformly distributed on the interval (0,1). This ensures that every positive integer has a positive probability of being chosen as n (assuming infinite precision for r).

If n coincides with any of the previous numbers (taken as input) the process is repeated.

`       % Do...while
  x     %   Delete. This deletes the candidate number from the preceding iteration.
        %   In the first iteration it takes input implicitly and deletes it.
  1     %   Push 1
  r     %   Push random number uniformly distributed on (0,1)
  /     %   Divide
  Xk    %   Round up (ceil). This is the candidate output. It will only be valid
        %   if it's not present in the input
  t     %   Duplicate
  G     %   Push input: forbidden numbers
  m     %   Ismember. This will be used as loop condition
        % End (implicit). If condition is true, next iteration
        % Display (implicit)

Python 3, 137 127 123 138 117 99 98 bytes

A named or unnamed function which returns an infinite iterable (such as a Python generator)

from random import*
def f(x=[],y=1):
 while y in x or.5<random():y+=1
 yield y;yield from f(x+[y])

• -10 bytes by putting the conditional in one line (Thanks, @Dennis)
• -4 bytes by initializing r at the beginning of the loop
• +15 bytes by remembering numbers can contain zeroes...
• -21 bytes by renaming randint, and moving the condition in the head of the inner loop
• -18 bytes by switching to a functional paradigm
• -1 bytes by moving from or ...>.5 to .5<random() (thanks, @JonathanAllan)

JavaScript, 62 bytes

A full program that picks a single random value in [0 .. 1] and expressed it as a continued fraction, omitting elements that have been encountered before. This would produce a really infinite sequence if the initial value had an infinite precision. In practice, we are limited to what can be expressed in IEEE-854 format.

for(x=Math.random(),o=[];;)o[n=1/x|0,x=1/x-n,n]||alert(o[n]=n)

Demo

Here is a demo limited to 50 values and writing to the console instead.

for(x=Math.random(),o=[],i=0;i<50;)o[n=1/x|0,x=1/x-n,n]||console.log(o[i++,n]=n)

Japt, 17 bytes

aA=(1/Mr)c)<0?A:ß

Try it online!

Python 2, 39 bytes

f=lambda l,s:sum({1/s//1}-l)or f(l,s/2)

Try it online!

Takes a list l of previous outputs (as a set) and a seed s that's a random real from 0 to 1.