Is it safe for the ChaCha8 nonce to be deterministic? ChaCha8 takes a 8 byte nonce (or IV) that should not be the same twice for the same key. Generating this nonce randomly makes me very very nervous for collisions.

Is it safe to generate this nonce deterministically?

For example the first 6 bytes could be the number of milliseconds since the Unix epoch, with the last 2 bytes being an unsigned counter wrapping around. This will prevent any collisions from happening for 9000 years if no more than 65535 streams get encrypted in a millisecond (things get more complicated if the same encryption key is being used by multiple machines/threads, but let's ignore that for now).
Yes, it is safe. The only requirement for the nonce in Salsa/Chacha is to be unique; being predictable is not an issue, so a counter is fine.

Like CodesInChaos indicated, I believe extending XSalsa20 to XChaCha20 would also work if you want to a larger nonce, but have nothing concrete so will leave the details to him/her.