We know that Energy must be negative for bound states (as the wavefunction must go to 0 at infinity) but when we are looking at potential wells, we also say that E must be greater than the minimum value of potential ($V_{min}$ ) for a normalisable solution, so don't we have a contradiction when the $V_{min}$ is positive or even 0?
I think I might've made a major mistake in my thought process but I can't figure out what that is, any insight will be greatly appreciated.
Since the potential is only defined up to an overall constant, you should be suspicious of any definitions that depend on the absolute value of $V(x)$. Thus, a statement like $E<0$ is meaningless, since only energy differences are physically meaningful quantities!
In general, bound states are those which have an energy less than the value of the potential at $\pm \infty$. Now, in some physical problems like the finite potential well and the hydrogen atom we assume that $V(x)\to 0$ as $x\to \pm \infty$, which is why it is often said that bound states have negative energy. However, it should be clear to you that this is certainly not the case in general!
Indeed, I am certain you already know of two famous counter-examples: the particle-in-a-box (the "infinite square well") and the harmonic oscillator. Both of these potentials have only bound states, and they certainly don't have negative energies! The fact that all their states are bound can now be explained using my earlier argument: since both these potentials blow up at $x\to\pm\infty$, all energies are less than $\lim_{x\to\pm\infty}V(x) = V_{\pm\infty}$, and therefore all states are bound.
To answer your specific question about the potential well, in order for your potential to be a "well" you would require it to have $V_\text{min} < V_{\pm\infty}$ (since otherwise it would be something like a "top-hat" potential which would have no bound states anyway). If you choose $V_{\pm\infty} = 0$, then $V_\text{min}$ must be less than zero in order for your potential to describe a "well". You could, of course, choose $V_{\pm\infty}=V_0>0$, but in this case bound states would be those that have an energy $E<V_0$.
See also the answers to these questions: What exactly is a bound state and why does it have negative energy? and Scattering vs bound states.
