Parametric contour plot?

Let's call $u=f_1(x)$ and $v=f_2(y)$. Do you want to plot $g(u,v)=1$ against $x$ and $y$, or $g(x,y)=1$ against $u$ and $v$? @bill's answer does the former. Here's a way to do the latter: Use ParametricPlot, and define the contour using MeshFunctions.

f1[x_] := Log[1 + x]
f2[y_] := Exp[y] - 1
g[x_, y_] := x^2 + y^2

ParametricPlot[{f1[x], f2[y]}, {x, -1.2, 1.2}, {y, -1.2, 1.2}, 
 MeshFunctions -> {Function[{u, v, x, y}, g[x, y]]}, Mesh -> {{1}}, 
 MeshStyle -> Directive[Opacity[1], Black]]

You can set PlotStyle -> None, BoundaryStyle -> None, Axes -> False if you want it to look more similar to the default ContourPlot.

Unfortunately, it seems that MaxRecursion doesn't help to improve the contour, so if you need better quality you'll have to increase PlotPoints.

It's simpler than you fear. First the command is ContourPlot... for a simple g, this will give you the circle of radius 1.

g[x_, y_] := x^2 + y^2;
ContourPlot[g[x, y] == 1, {x, -2, 2}, {y, -2, 2}]

Now say you have the two functions f1 and f2

f1[x_] := Log[x];
f2[y_] := Exp[y];
ContourPlot[g[f1[x], f2[y]] == 1, {x, -2, 2}, {y, -2, 2}]

Now you get the contour plot of the nested functions.

You can also post-process the output of ContourPlot to transform the contour lines using a transformation that depends on two functions t1 and t1:

postProcess[t1_, t2_, col_: LightBlue] := Show[# /. GraphicsComplex[c_, p_] :> 
   GraphicsComplex[Transpose[{t1 /@ #, t2 /@ #2} & @@ Transpose[c]], p], 
    PlotRange -> All] /. Line[x_] :> {Thick, Line[x], col, Polygon[x]} &

Using the example in @Rahul's answer with a slight modification:

f1[x_] := Re @ Log[1 + x]
f2[y_] := Re[Exp[y] - 1]
g[x_, y_] := x^2 + y^2

cp = ContourPlot[g[x, y] == 1, {x, -1.2, 1.2}, {y, -1.2, 1.2}, 
   FrameLabel -> {{Style["y", 16], ""}, {Style["x", 16], ""}},  ImageSize -> 400];

Row[{cp, Show[postProcess[f1, f2] @ cp,  FrameLabel -> 
  {{Style[Subscript[f, 2][y], 16], ""}, {Style[Subscript[f, 1][x], 16], ""}}]}, 
 Spacer[10]]

cp2 = ContourPlot[g[x, y], {x, -1.2, 1.2}, {y, -1.2, 1.2}, 
  Contours -> {.1, .5, 1}, FrameLabel -> {{Style["y", 16], ""}, {Style["x", 16], ""}}, 
  ImageSize -> 400, ContourShading -> None];

Row[{cp2, Show[postProcess[f1, f2] @ cp2,  FrameLabel -> 
  {{Style[Subscript[f, 2][y], 16], ""}, {Style[Subscript[f, 1][x], 16], ""}}]}, 
 Spacer[10]]