Interesting that this question came yesterday, since I just finished an implementation yesterday that does this.
Just to start of, let me know that while my education background is from scientific computing, all work I have done since graduating, including my current Ph.D. work, has been in computational electromagnetics. So, I guess our backgrounds are somewhat similar, since you also appear to be looking at physics (based on your profile).
First of all, what you are looking for, as Guido Kanschat has already mentioned in a comment, is called Flexible GMRES or FGMRES. The reference, including pseudocode, is in . While I sometimes find numerical SIAM papers a bit hard to read,  (and most of Saad's other work, including the brilliant [B1], apparently legally available for free online) is different; the paper is a fascinating read, very clearly written and with a few nice examples and suggestions for applications.
FGMRES is easy to implement, particularly if you already have a working RIGHT preconditioned GMRES. Note the keyword RIGHT here - if you have a LEFT preconditioned GMRES, i.e. you are used to solving MAx=Mb, then you have to make a few modifications. Compare [B1,Algorithm 9.4 on pg. 282] to [B1,Algorithm 9.5,pg. 284]. You can also find the FGMRES in [B1,Algorithm 9.6, pg. 287], but I would really encourage you to read  as it is short, well written and still has many interesting details.
What does it do
FGMRES basically allows you to switch preconditioners for every iteration, if you wish. One of the applications for this is that you can use some preconditioner that works very well when you are far away from the solution, and then switch to another one when you get closer. , which I have not read in detail, appears to discuss something similar to this.
However, the most interesting application in my case was that you could use a (preconditioned) GMRES as a preconditioner for your FGMRES. This is the reason behind the typical name for FGMRES, "inner-outer GMRES". Here, "outer" refers to the FGMRES solver, which (as preconditioner) uses an "inner" solver.
So, how good is this in practice?
In my case, this worked absolutely brilliant. In the inner loop, I "solve" a reduced-complexity formulation of my problem. On its own, this solution is far too inaccurate for our use, but it works absolutely great as a preconditioner. Note the "" around "solve" - there is no need to run the inner solver to convergence, since you are only looking for rough approximations. In my case, I went from using 151 iterations, each costing 64 seconds, to 72 iterations, each costing 79 seconds (I used a fixed 5 iterations in the inner GMRES). That is a total saving of an hour, with no loss of accuracy and very little coding work since we already had a functioning GMRES which we just made recursive.
For some applications of this stuff, demonstrating the potential performance, see  (which actually uses a three-level FGMRES, so FGMRES, with FGMRES as inner, with GMRES as inner-inner) and , which might be too application specific for your use, but contains several interesting test cases.
 Y. Saad, “A flexible inner-outer preconditioned GMRES algorithm,” SIAM J. Sci. Comp., vol. 14, no. 2, pp. 461–469, Mar. 1993. http://www-users.cs.umn.edu/~saad/PDF/umsi-91-279.pdf
 D.-Z. Ding, R.-S. Chen, and Z. Fan, “SSOR preconditioned inner-outer flexible GMRES method for MLFMM analysis of scattering of open objects,” Progress In Electromagnetics Research, vol. 89, pp. 339–357, 2009. http://www.jpier.org/PIER/pier89/22.08112601.pdf
 T. F. Eibert, “Some scattering results computed by surface-integral-equation and hybrid finite-element-boundary-integral techniques, accelerated by the multilevel fast multipole method,” IEEE Antennas and Propagation Magazine, vol. 49, no. 2, pp. 61–69, 2007.
 Ö. Ergül, T. Malas, and L. Gürel, “Solutions of Large-Scale Electromagnetics Problems using an Iterative Inner-Outer Scheme with Ordinary and Approximate Multilevel Fast Multipole Algorithms,” Progress In Electromagnetics Research, vol. 106, pp. 203–223, 2010. http://www.jpier.org/PIER/pier106/13.10061711.pdf
[B1] Y. Saad, Iterative Methods for Sparse Linear Systems. SIAM, 2003. http://www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf