There are smooth schemes which don't have this property, usually called resolution property. A simple example is $X=\mathbb{A}^n \cup_{\mathbb{A}^n \setminus \{0\}} \mathbb{A}^n$, the affine $n$-space with a double origin, and $n \geq 2$. A locally free sheaf on $X$ pulls back to two locally free sheaves on $\mathbb{A}^n$ which become isomorphic when restricted to $\mathbb{A}^n \setminus \{0\}$. Since every locally free sheaf on $\mathbb{A}^n$ is free (Quillen-Suslin Theorem), the isomorphism corresponds to an invertible matrix of global sections of $\mathbb{A}^n \setminus \{0\}$, which by Hartog's Lemma coincide with the global sections of $\mathbb{A}^n$ (here we use $n \geq 2$). Hence, the isomorphism of the two free sheaves extends on $\mathbb{A}^n$, which means that the original locally free sheaf on $X$ is free. It follows that not every coherent sheaf on $X$ is a quotient of a locally free i.e. free sheaf, because otherwise $\mathcal{O}_X$ would be ample and therefore $X$ would be separated.
On the other hand, many schemes have the (strong) resolution property, for example divisorial schemes (M. Borelli, Divisorial varieties) - including projective schemes and any separated noetherian locally factorial scheme (SGA 6, Exp. II, Proposition 2.2.7), as well as any separated algebraic surface (P. Gross. The resolution property of algebraic surfaces). For further results see (P. Gross, Vector bundles as generators on schemes and stacks. PhD thesis) and (B. Totaro, The resolution property for schemes and stacks). For algebraic stacks, there is a useful criterion which depends on a presentation (D. Schäppi, A characterization of categories of coherent sheaves of certain algebraic stacks).
It seems to be an open problem if there is a variety (separated scheme of finite type) which doesn't have the resolution property.
For these kinds of questions, if you can see how to establish an isomorphism stalkwise, the key thing you need to do to promote this to a complete proof is to construct a morphism between the sheaves that you are trying to prove are isomorphic.
Once you have a morphism, in order to check that it is an isomorphism, you can work on stalks; and then hopefully the induced morphism equals to isomorphism you've already constructed. (If what you've done is sufficiently natural, then this should work out). In this particular case, there's likely an argument that avoids working with stalks altogether, but since you've already thought about them, it makes sense to incorporate them into your argument; and in any case, the strategy I'm suggesting is a very common one.
So, you want a natural morphism $f^*(\mathscr E^{\vee}) \to (f^*\mathscr E)^{\vee}$
(intuiting the correct direction in which to construct the desired morphism is one of the subtleties of this proof strategy, but can normally done by a bit of trial-and-error).
That is, we need a pairing $$f^*(\mathscr E^{\vee}) \times f^*\mathscr E \to \mathscr O_X,$$ or equivalently a morphism $$f^*(\mathscr E^{\vee}) \otimes_{\mathcal O_X} f^*\mathscr E \to \mathscr O_X.$$ (Judicious unwinding of definitions, as in this case, where I've unwound the definition of $(f^*\mathscr E)^{\vee})$, is also a typical aspect of such an argument.)
But just using properties of pull-backs and tensor products, you can see that there is a canonical isomorphism
$$f^*\mathscr E^{\vee}\otimes_{\mathscr O_X} f^*\mathscr E \cong f^*(\mathscr E^{\vee} \otimes_{\mathscr O_Y} \mathscr E).$$
So the desired morphism can be obtained by pulling back the canonical morphism
$$\mathscr E^{\vee} \otimes_{\mathscr O_Y} \mathscr E \to \mathscr O_Y$$ via $f$.
Now that you have a morphism from $f^*(\mathscr E^{\vee})$ to $(f^*\mathscr E)^{\vee}$, you can pass to stalks to check it is an isomorphism. But on stalks,
it will surely agree with the isomorphism you've already discovered (since this is the only natural isomorphism in this context).
Best Answer
As Jesko says, already for line bundles there are problems. The easiest example is probably $\mathscr{O}_{\mathbf{P}^n_k}(1)$ and its dual $\mathscr O(-1)$. The first has lots of nonzero global sections, but the second has none; they can't even be non-canonically isomorphic.
One interesting thing to think about, which I saw pointed out in a book review by Kollár, is that in differential geometry one can choose a metric on any vector bundle and use that to identify $E \simeq E^\vee$. So this is a good example of how algebraic geometry differs.