Generating non-repeating N-bit IVs, which are indistinguishable from randomness
I suppose the easiest way to generate these initialization vectors is to use a 64-bit block cipher (like Blowfish or DES/3DES), and encrypt sequential values of a 64-bit counter.

Of course, the "indistinguishable from true randomness" property of good block ciphers is only valid if the attacker can't observe much more than $2^{32}$ such initialization vectors, as then a truly random sequence would start to show duplicate elements, while your one would not, by your requirement.

Actually, if the only requirement is a nonce, and your protocol messages arrive in sending order (like over a TCP connection), you don't have to send it with the actual stream data, as long as the other side has the necessary information to generate it. Then a simple counter, counted up at both sides (and never transmitted), will do nicely (and you don't have to think about another key which needs to be managed).