First compute a Cholesky factorization of the covariance matrix. Now your tentative new covariance matrix is a rank-2 update of the old, 
$$
M_{new}=M_{old}+\frac{1}{n}x_{new}x_{new}^T-\frac{1}{n}x_{old}x_{old}^T.
$$
You can use Sylvester's formula [here][1] to compute the determinant of the update; for this you'll only need to solve a linear system, which is $O(n^2)$ using your Cholesky factorization.

Then when your "replacement" take place for real you just have to update the Cholesky factorization, and there are algorithms to do that (low-rank updates of Cholesky factorization) in $O(n^2)$ as well. Check Matlab's `cholupdate` for instance.

So you pay $O(n^3)$ at the first step and then $O(n^2)$ per step.

EDIT: better and clearer algorithm

  [1]: https://en.wikipedia.org/wiki/Matrix_determinant#Sylvester%2527s_determinant_theorem