I apologize in advance as I am not very experienced with any formal notion of randomness.
The title says most of it: I want to generate a random integer within a reasonable time, where every integer can appear, whether with equal frequency or not isn't important. As an add on, computer memory is not an issue, as even with infinite memory space to store these generated numbers it isn't obvious how one could do this. I haven't made any progress in actually figuring out a proper algorithm but here are my observations.
If you can generate any real number randomly then you could use functions like the floor function to generate any integer. If you could randomly generate any real number between any interval $[a,b]$, then you could use asymptotic functions like $\tan$ to generate any real number.
In general if I have a set S which has a larger or equal cardinality to the integers, and I can randomly generate an element within S, then I can randomly generate any integer by mapping members of S onto the integers.
I know that there are sequences, such as the prime gap sequence, which are random and contain arbitrarily large integers, but are not computable easily.
However that is about it with regards to what I can think of. I would not be surprised if there was no easy solution to the problem, but if anyone has a reason as to why this is not possible I would like to hear as well.
Best Answer
The arbitrary size has no meaning since the computation cannot halt!
Consider that you toss a coin for every bit of the random integer, then you can see that the coin tossing is never-ending.
One should be careful when playing with the arbitrary size. Mathematically you can say that let $x$ be a random integer, i.e. $x \stackrel{R}{\leftarrow} \mathbb Z$ , however, when you try to find a value of this you will face the generation of it. If you want a uniform random integer then obviously it will fail!
Now assume that you have a limit like $0\color{red}{<} x \leq 2^L$ then you can use LFSR's to generate random numbers in the range. If an LFSR with size $L$ is maximal then it is periodic and it has a period of $2^L-1$. In this period it visits all possible $L$-bit numbers except the all-zero state. You can get a seed from the time and start using it.
Note that LFSR is far from away from being a Cryptographically Secure Random Pseudo Generator (CSPRNG). Having just $2L$ bit output from the LFSR is enough to determine the next bits due to the Berlakamp-Massay algorithm - and actually, Gaussian elimination is enough, however, BM is a lot faster-.