Is there any algorithm for determining 3d position in such case? Suppose I have the following image (i.e. I have the coordinates of all points in 2d so I can regenerate lines and check where they cross each other)

Now suppose I have another image of what I know to be the same lines:

How can I determine plane rotation and Z depth on second image (asuming first one's center was in point (0,0,0) with no rotation)?
 A: What you see in the second image is a projection of the first, after a rotation. So treat it exactly like that. Meaning, you have 4 lines in $\mathbb{R}^3$. You know their equations. Furthermore, you have another 4 lines in $\mathbb{R}^2$ corresponding to the second image.
To solve, parameterize the family of possible 4 lines in $\mathbb{R}^3$ that project onto the 4 lines in $\mathbb{R}^2$. Find the matrix that takes the original 4 lines to generic quadruple in the mentioned family. Now write equations to ensure that matrix is actually a rotation. You should have enough information for there to be at most one quadruple that can actually be gotten from the original lines. If not, then your question has multiple answers.
A: This is a common computational problem in computer vision.
Here are two sources (among many).

(1) Aaron Bobick, Georgia Tech: "Two arbitrary views of the same scene."
  PDF download of lecture slide deck.
  
            
  

            
  
  CS 4495 Computer Vision: Homographies.
  


Another source:

(2) Jana Kosecka, George Mason Univ.: Uncalibrated Two-View Geometry (PDF download).
  
            
  


