See "Finding the distance between two circles in three-dimensional space," by C.A. Neff, in the IBM Journal of Research and Development, Volume 34, Number 5, Page 770 (1990). IBM link. From the Abstract:
We show, by combining a theorem about solvable permutation groups and some explicit calculations with a computer algebra system, that, in general, the distance between two circles is an algebraic function of the parameters defining them, but that this function is not solvable in terms of radicals.
Another source is David Eberly's "Distance Between Two Circles in 3D," PDF link. His unpublished note gives explicit instructions for the computation, without analyzing its algebraic complexity too carefully. He does say that a critical equation
can be reduced to a polynomial of degree 8 whose roots ... are the candidates to provide the global minimum...