In[409]:= PolynomialReduce[z^4 + z^2 + 4, z^2 - x, {z, x}][[2]]
 
 Out[409]= 4 + x + x^2

This is similar to the Solve approach in that both use algebraic means to effect the substitution. But one can be a bit more general using PolynomialReduce (by taking advantage of term orders, say).

For further detail on this approach, might have a look at some responses [here](http://stackoverflow.com/questions/6210321/question-on-smart-replacing-in-mathematica) and [there](http://stackoverflow.com/questions/5008764/how-to-reduce-the-number-of-independent-variables-in-mathematica).