Consider the following problem from Nielsen and Chuang's Quantum Computation and Quantum Information:
Explain how a device which, upon input of one of two non-orthogonal quantum states $\left|\psi\right>$ or $\left|\phi\right>$ correctly identified the state, could be used to build a device which cloned the states $\left|\psi\right>$ and $\left|\phi\right>$, in violation of the no-cloning theorem. Conversely, explain how a device for cloning could be used to distinguish non-orthogonal quantum states.
I know that this problem has already been posted at least two times here and here, but I am not satisfied with the answers to the first part given there. As you can see, all answers to the first part basically tell you to use the device to distinguish between $\left|\psi\right>$ and $\left|\phi\right>$ and then just prepare an identical state. However, nowhere does this exercise say that we know how to prepare states $\left|\psi\right>$ and $\left|\phi\right>$. Moreover, preparing an identical state is not the same as cloning. A cloning device has to be able to replicate a state without having any prior knowledge about its "internal" structure. With this in mind, I am posting this problem once again.
Here is my attempt to address this problem. Let us say that we have two non-orthogonal states $\left|\psi\right>$ and $\left|\phi\right>$. We can measure $\left|\phi\right>$ in the basis of $\left|\psi\right>$, and feed the result to our magical device. Since $\left|\phi\right>$ is non-orthogonal to $\left|\psi\right>$, there is non-zero probability that measurement will give us another $\left|\psi\right>$. In this case the device will identify it as $\left|\psi\right>$, which means we have created a clone. If the measurement projects $\left|\phi\right>$ to some other state $\left|\psi'\right>$, orthogonal to $\left|\psi\right>$, then the device will not identify it as $\left|\psi\right>$, and we can repeat the process by measuring $\left|\psi'\right>$ again in the basis of $\left|\phi\right>$, which will create another state non-orthogonal to $\left|\psi\right>$.
This solution is also quite flimsy for the following reasons. First, I am not sure if an arbitrary unknown state can be used as a basis for measurement. Second, this solution never actually used the device to distinguish between $\left|\phi\right>$ and $\left|\psi\right>$. It only used it to distinguish between $\left|\psi\right>$ and not $\left|\psi\right>$, but it is unclear what happens if we try to feed a state other than $\left|\phi\right>$ and $\left|\psi\right>$ to the device, so this way was probably not implied by the authors of the exercise.
Any ideas?