I have two three-dimensional vectors that each represent the orientation of an object in space. I can calculate the angle between them by using the dot product, which yields $\cos(\theta)$ where $\theta$ is the angle between the two vectors in the plane that they define in 3D space ($\phi$ is the "other angle" for rotating the plane itself in any direction).
Now here's my problem: suppose I'm given a new 3D dot product $\cos(\theta)$ and told to change the relative orientation of the two 3D vectors so that their $\cos(\theta)$ matches the new one I'm given. I know the original coordinates and original $\cos(\theta)$ of both vectors. Is there a way to change the coordinates of one vector so that the dot product becomes the new one? Given that the vectors are three-dimensional and there is another angle $\phi$ (not just $\theta$), is this even a well-defined problem with a unique solution?
Let's assume the vectors are unit vectors (you did not say they are, but since you say the dot product is just $\cos(\theta)$, it seems you likely meant to use unit vectors). The angle between the given vectors $v,w$ is $\theta$ and you want a new vector $v'$ such that the angle between $v'$ and $w$ is a given angle $\theta'.$
For convenience in notation, let $c = \cos(\theta)$ and let $c' = \cos(\theta')$. We have $$ v \cdot w = c. $$
Let $v' = av + bw$, where $a$ and $b$ are scalar factors to be determined, such that $v'$ is a unit vector. That is, $v'$ will be a linear combination of $v$ and $w,$ which means it will be in the same plane as those two vectors.
We want $ v' \cdot w = c' $ and $ v' \cdot v' = 1.$
But
$$ v' \cdot w = (av + bw) \cdot w = av\cdot w + bw \cdot w = ac + b $$
and
$$ v' \cdot v' = (av + bw) \cdot (av + bw) = a^2v\cdot v + 2abv \cdot w + b^2w \cdot w = a^2 + b^2 + 2abc .$$
This gives us a system of two equations in two unknowns:
\begin{align} ac + b &= c',\\ a^2 + b^2 + 2abc &= 1. \end{align}
Substituting $b = c' - ac$ in the second equation, $$ a^2 + (c' - ac)^2 + 2a(c' - ac)c = (1 - c^2)a^2 + c'^2 = 1. $$
Therefore
$$ a^2 = \frac{1 - c'^2}{1 - c^2} = \frac{\sin^2(\theta')}{\sin^2(\theta)}. $$
Note that there are typically two values of $a$ that would solve this equation. In order to minimize the perturbation of $v,$ we would like $v$ and $v'$ to be on the same side of $w.$ We can achieve this by choosing the positive value of $a.$ Assuming that the angle between vectors is always in the interval $[0,\pi],$ the sine is always non-negative, so we end up with $$ a = \frac{\sin(\theta')}{\sin(\theta)}. $$
Plug this into $b = c' - ac$ to find $b.$
Here is a way to visualize this:
Consider $w$ as the vector to the north pole of a sphere from the center of the sphere; then the vectors at angle $\theta'$ to $w$ are vectors from the center to a line of latitude. The vector $v$ points to some point on the sphere; to get from that point to the line of latitude along a path of minimum distance, you go either due "north" or due "south" until you reach the line of latitude. That is the minimum perturbation to $v$ to reach the desired vector $v'.$ That is what is accomplished by the linear combination shown above.