For your question (1), there is an efficient algorithm  known for finding an embedding of a graph in the plane if an embedding exists.
This, however, might not be the end of the story. You may want to get an embedding where every edge is a straight line segment. It is known that such an embedding always exists if there is an embedding and there are no duplicate edges, this is called Fáry's theorem In fact, such an embedding can also be found with an efficient algorithm .
Your question (3) is turning a planar embedding to a polyhedron embedded in the space. This has an easy special case: namely if all faces of the planar embedding are triangles and all edges are straight segments. In this case, you can get a polyhedron embedding by slightly bending the plane so you get a sphere with a large radius, then fixing the vertexes and straightening the edges and faces.
(Update) The general case is known as Steinitz's theorem, which states that any 3-connected planar graph is the edge graph of a convex polyhedron. The proof of this theorem isn't trivial, but may give you some insight as to how to turn a planar embedding to a polyhedron. (Note that for 3-connected planar graphs, there's always essentially only one planar embedding, not counting inversions which lets you put infinity into any face, and mirror images.)
As for (4), if you start from a convex polyhedron, you can get a planar embedding, not necessarily with straight edges, by first projecting the vertexes and edges of the polyhedron to a sphere inside the polyhedron, then projecting that sphere to the plane.
 John Hopcroft, Robert Tarjan, "Efficient Planarity Testing", Journal of the Association for Computing Machinery, 21/4 (1974), 549, scanned copy at http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/Planarity%20testing.pdf
 Walter Schnyder, "Embedding planar graphs on the grid", SODA '90 Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, (1990), 138-148, scanned copy at http://departamento.us.es/dma1euita/PAIX/Referencias/schnyder.pdf , ISBN:0-89871-251-3. Abstract: "We show that each plane graph of order n ≥ 3 has a straight line embedding on the n − 2 by n − 2 brid. This embedding is computable in time O(n). A nice feature of the vertex-coordinates is that they have a purely combinatorial meaning."