Replace heads to match a pattern

replaceHeads[expr_, h_, new_] := 
 ReplacePart[expr, Thread[Position[expr, h] -> new]]
replaceHeads[f[f[f[]]], f, {a, b, c}]
(*a[b[c[]]]*)
replaceHeads[f[f[], f[]], f, {a, b, c}]
(*a[b[], c[]]*)

Quick and dirty:

replaceHeadWithSet[expr_, h_, heads_] := Module[{j = 0},
  ReplaceAll[expr, 
   h :> (j = Mod[j + 1, Length[heads], 1]; heads[[j]])]]

Example:

replaceHeadWithSet[f[f[f[], f[]]], f, {a, b, c}]

(* Out[84]= a[b[c[], a[]]] *)

A different interpretation: the heads to replace are not all the same but the structure is fixed.

rep[h_@x___, {n_, r___}] := n @ rep[x, {r}]

rep[x___, {}] := x

Use:

rep[f[g[h[]]], {a, b, c}]

a[b[c[]]]