Yes, this should be solvable and should be doable in a reasonable amount of computation time, using a pretty cool homomorphic cryptosystem.
Here is one approach: the participants jointly pick a random number $y$, publicly commit to $y$, and then they all prove/check in zero knowledge that $y$ is different from their numbers. If it isn't, they go back to the beginning and try again, until they have found a choice that differs from all their numbers.
The zero-knowledge proof part can be made efficient using the following paper:
Boneh, Goh, and Nissim build a public-key encryption algorithm $E(\cdot)$ that allows you to evaluate any 2-DNF formula on encrypted values. In other words, if you have $E(x_1),\dots,E(x_m)$, where $x_1,\dots,x_m$ are boolean values, and if you have a 2-DNF formula $\Psi$, then you can compute $E(\Psi(x_1,\dots,x_m))$ from $E(x_1),\dots,E(x_m)$. The computation can be done quite efficiently. This is a very cool kind of homomorphic property, and it is very useful here.
In particular, if we have two numbers $y,z$, notice that the condition $y \ne z$ is a 2-DNF formula on the bits of $y,z$: $y\ne z$ is equivalent to
$$(y_1 \land \neg z_1) \lor (\neg y_1 \land z_1) \lor \dots \lor (y_\ell \land \neg z_\ell) \lor (\neg y_\ell \land z_\ell),$$
where $y_i$ is the $i$th bit of $y$ and $z_i$ the $i$th bit of $z$.
Moreover, if we have $n+1$ numbers $y,z_1,\dots,z_n$, and the ciphertexts of each bit of each number were encrypted separately using the Boneh-Goh-Nissim, we can check the condition $(y \ne z_1) \land \dots \land (y \ne z_n)$. Here is how. Let the bit $b_i$ be $1$ if $y \ne z_i$, and $0$ otherwise. Notice that we can compute $E(b_i)$ and the encryptions of the bits of $y,z_i$, using the ideas above and the homomorphicity of $E(\cdot)$. Define $k=b_1+b_2+\dots+b_n$. Notice that we can also compute the ciphertext $E(k)$ from $E(b_1),\dots,E(b_n)$, by the homomorphism properties of $E(\cdot)$. Now the condition $(y \ne z_1) \land \dots \land (y \ne z_n)$ holds if and only if $k=n$. Thus, to check the condition, we can decrypt $E(k)$ and check whether we get $n$ or not.
In addition, in the case where we know $z_1,\dots,z_n$ are distinct, the procedure does not reveal anything about the underlying $z_1,\dots,z_n$, beyond whether $y$ is equal to one of them. That's because $k$ will be either $n$ or $n-1$; it will be $n$ if $y$ is different from all of them, or $n-1$ if $y$ is equal to one of them. So the decryption of $E(k)$ does not disclose anything beyond whether $y$ is equal to one of the $z_i$'s (and if it is, it does not disclose which $z_i$ it is equal to).
Therefore, we immediately obtain a solution, using a threshold version of the Boneh-Goh-Nissim scheme:
The parties jointly generate a public/private keypair for the Boneh-Goh-Nissim cryptosystem, such that each party ends up with a share of the private key, no party (or coalition of parties) knows the private key, and everyone knows the public key. Their paper describes how to do that. This only needs to be done once.
Each party writes his/her private number in binary notation, separately encrypts each bit with the Boneh-Goh-Nissim cryptosystem, and then publishes all of those ciphertexts. In more detail, call party $i$'s secret number $z_i$. Write it in binary as the bits $z_{i,1},\dots,z_{i,\ell}$, then publish $E(z_{i,1}),\dots,E(z_{i,\ell})$, where $E(\cdot)$ represents Boneh-Goh-Nissim encryption under the public key established in step 1. Each party separately does this. This is also a one-time step that never needs to be repeated.
The parties now jointly generate a random number $y$, using standard methods. They encrypt each bit of $y$ separately, using the Boneh-Goh-Nissim scheme. (For instance, you can have one party do the encryption and then prove that he/she did it correctly.)
Now, check whether $y$ is equal to any of $z_1,\dots,z_n$. This can be done using the techniques described above. They can all compute $E(k)$, then they use the threshold decryption procedure to jointly decrypt $E(k)$ and learn $k$. The value of $k$ (either $n$ or $n-1$) reveals whether $y$ is different. If $y$ is different, they are done, and they output $y$. Otherwise, they go back to step 3 and try again.
How long will this procedure take? If there are $n$ parties, and the range of values covers $x$ possible values, then each iteration has a $1 - n/x$ probability of success and a $n/x$ probability of leading to a retry. Therefore, on average we need to retry $x/n$ times. For instance, if you're trying to pick a random number from $[0..200]$, then as long as there are no more than 100 parties, on average only 2 iterations are needed.
How much side information is disclosed? None of the parties ever discloses their secret number. However, any time we have to retry the procedure, an eavesdropper does learn that the number $y$ we were using must be the secret number of one of the parties (but the eavesdropper doesn't learn which party it was). This is a downside. This downside can be removed using more sophisticated methods (e.g., a way for the parties to jointly choose the random number $y$ without any of them knowing the value of $y$, but they all know the encryption of the bits of $y$), if you care.
As DrLecter helpfully points out:
BGN requires pairings over composite order bilinear groups (which are terribly slow to work with), [so] it may be worth to mention Freemans' product group approach, that among others allows to transfer BGN into a prime order setting and nicely increases performance by several orders of magnitude.
