I have currently used displacement mapping (vertex texture fetching) to deform a 2D plane using a perlin noise generated texture. But now I would like to animate a 3D landscape instead of a 2D plane. Any ideas on how to build a 3D landscape using displacement mapping?

i dont get the question, a 3d landscape is a deformed 2d plane.
(im thinking of dispacement mapping like in paralax mapping, adding 3d to 2d, but maybe thats wrong).
I gues youre not simply looking to genreate a noise texture and use that as heightmap ??

Well the input is a 2D mesh, then I use a noise image to replace the vertices in the 2D map, and it definitely looks changed but when I rotate it its still in 2D.

If your goal is to start of with an XxY grid of polygons (triangles/quads) with all equal heights (y=0), and map all the heights according to some image, then Im not sure why youre talking displacement mapping. just create a heightmap...

Is this you goal? creating a heightmap??
or something else? like create a 3d feel on a 2d plane / single quad (bumpmapping/ paralaxmapping)

im not sure what you mean by 'replacing' vertices. do you mean 'translate' ??

oh maybe this is more to the point...
if your input is 2d, and you want to project/create 3d, then your data structure should be able to 'add' the component.
e.g. a vertex2d has xy components, so projections using only this structure will never contain a 3rd component z... or rather, if you can only hold xz values, and never an y (y is more intitive for height, but can also be any other of course), then offcourse rendering this will always be constrained to the xz plane on y=0.

I would like to create something like this:

http://www.ozone3d.net/tutorials/vertex_displacement_mapping.php

But as you point out I need to apply the noise map to something with a "potential" 3. coordinate.

In a general sense, displacement mapping has nothing to do with the(primitive) vertices of a mesh. It can also apply to fragments
Basically its 'moving stuff around' and in your case there is no specific relation, besided image data, which is independant from anything else, so thats easy enough (in contrast very specific displacement like e.g. based on normal/light info)

To create your heigtmap, generate a grid with xyz coords, where all y's are 0, and x,z is 'correcttly' placed. (thus a flat grid)

then cycle all the xy coords again, now use them as (dual) input to the giveHeight(x,z) function to fill in the last (y) coord.
This function is in it simplest heightmap for textureColor(x,z) / 255.0f * maxheightForTerrain, but can be as fancy as you want.
Also, in this simple case, the y is the only coord 'adjusted', but this can also be anything you want, (if y grows, x shrinks or something..or even more dimension, is y grows, the color changes)

hope that helps