(Edit notes: I reorganized this after freaking out at its length.)
Literature on coordinate descent can be a little hard to track down. Here are some reasons for this.
Many of the known properties of coordinate methods are captured in umbrella theorems for more general descent methods. Two examples of this, given below, are the fast convergence under strong convexity (hold for any $l^p$ steepest descent), and the general convergence of these methods (usually attributed to Zoutendijk).
Naming is not standard. Even the term "steepest descent" is not standard. You may have success googling any of the terms "cyclic coordinate descent", "coordinate descent", "Gauss-Seidel", "Gauss-Southwell". usage is not consistent.
The cyclic variant rarely receives special mention. Instead, usually only the best single choice of coordinate is discussed. But this almost always gives the cyclic guarantee, albeit with an extra factor $n$ (number of variables): this is because most convergence analyses proceed by lower bounding the improvement of a single step,and you can ignore the extra coordinates. It also seems difficult to say anything general about what cyclic buys you, so people just do the best coordinate and the $n$ factor can usually be verified.
Rate under strong convexity. The simplest case is that your objective function is strongly convex. Here, all gradient descent variants have the rate $\mathcal O(\ln (1/\epsilon))$. This is proved in Boyd & Vandenberghe's book. The proof first gives the result for gradient descent, and then uses norm equivalence to give the result for general $l^p$ steepest descent.
Constraints. Without strong convexity, you have to start being a little bit careful. You didn't say anything about constraints, and thus in general, the infimum may not be attainable. I'll say briefly on the topic of constraints that the standard approach (with descent methods) is to project onto your constraint set each iteration to maintain feasibility, or to use barriers to roll the constraints into your objective function. In the case of the former, I don't know how it plays with coordinate descent; in the case of the latter, it works fine with coordinate descent, and these barriers can be strongly convex.
More specifically to coordinates methods, rather than projecting, many people simply make the coordinate update maintain feasibility: this for instance is exactly the case with the Frank-Wolfe algorithm and its variants (i.e., using it to solve SDPs).
I'll also note briefly that the SMO algorithm for SVMs can be viewed as a coordinate descent method, where you are updating two variables at once, and maintaining a feasibility constraint while you do so. The choice of variables is heuristic in this method, and so the guarantees are really just the cyclic guarantees. I'm not sure if this connection appears in standard literature; I learned about the SMO method from Andrew Ng's course notes, and found them to be quite clean.
General convergence guarantee. What I know in this more general setting (for coordinate descent) is much weaker. First, there is an ancient result, due to Zoutendijk, that all these gradient variants have guaranteed convergence; you can find this in the book by Nocedal & Wright, and it also appears in some of Bertsekas's books (at the very least, "nonlinear programming" has it). These results are again for something more general than coordinate descent, but you can specialize them to coordinate descent, and then get the cyclic part by multiplying by $n$.
More specifically to cyclic coordinate descent, there's a paper by Luo & Tseng titled "On the convergence of the coordinate descent method for convex differentiable minimization". These results require the infimum to be attainable. There are no rates here, only convergence guarantees, but these results have been applied to some more specialized settings to get rates; for instance, in boosting (in the special case that the infimum is attainable), Warmuth, Mika, Raetsch, and Warmuth ("on the convergence of leveraging") were able to show rates of $\mathcal O(\ln(1/\epsilon))$.
There are some more recent results on coordinate descent, I've seen stuff on arXiv. Also, luo&tseng have some newer papers. but this is the main stuff.
More convergence rates in the special case of boosting. Due to its importance, there has been other specialization in the case of boosting. This is a pretty severe special case because your objective can be written $\sum_{i=1}^m g(\langle a_i, \lambda\rangle)$ where $g$ is a (convex) univariate function and the $(a_i)_1^m$ are fixed vectors ($\lambda$ is the optimization variable). Bickel, Ritov, and Zakai ("some theory for generalized boosting algorithms") showed you can get $\exp(1/\epsilon^2)$ in general, and there are more recent results by other people showing $\mathcal O(1/\epsilon)$. The difficulty in these is that the infimum is not assumed attainable.
The issue with exact updates. Also, it is very often the case that you do not have a closed form single coordinate update. Or the exact solution may simply not exist. But fortunately, there are lots and lots of line search methods that get basically the same guarantees as an exact solution. This material can be found in standard nonlinear programming texts, for instance in the Bertsekas or Nocedal&Wright books mentioned above.
Vis a vis your second paragraph: when these work well.
First, many of the above mentioned analyses for gradient work for coordinate descent. So why not always use coordinate descent? The answer is that for many problems where gradient descent is applicable, you can also use Newton methods, for which superior convergence can be proved. I don't know of a way to get the Newton advantage with coordinate descent. Also, the high cost of Newton methods can be mitigated with Quasinewton updates (see for instance LBFGS).
Second, the place where these methods shine is where the presumed solution is sparse (in the $l^0$ sense). Of course, there are NP-hardness issues with this kind of sparsity, but the point is that if you run $k$ iterations, you have $k$ nonzero entries. These facts generalize to, say, using coordinate methods with SDP solvers, where each iteration you throw in a rank 1 matrix, thus with $k$ iterations you have a rank $k$ iterate. There is a great paper on this topic, by Shalev-Shwartz, Srebro, and Zhang, titled "trading accuracy for sparsity in optimization problems with sparsity constraints". Most specifically to the second paragraph of your question, this paper gives further properties on $f$ that allow fast convergence and good sparsity (true to its title).
