Why can we have non-integer frequency bins in FFT?
Frequencies in DFT, $\omega = \frac{2\pi}{N}k, \ k = 0,1,2,...,N-1 $, only depends on the Length $N$ of DFT, and nothing else.


$$X[k] = \sum^{N-1}_{n=0}x[n]e^{-j\frac{2\pi}{N} nk}, \qquad k = 0,1,2,...,N-1$$

It is very important to understand this expression as the projection of time-domain finite length sequence $x[n], n=0,1,2,3,...,N-1$, of length $N$, onto orthogonal Discrete Fourier Basis Vectors $W_k^{N} = e^{j\frac{2\pi}{N}nk}, k=0,1,2,...,N-1$. And, the DFT Coefficients $X[k]$ are the projection coefficients actually on the $k^{th}$  basis vector. So, with this idea in mind, we can say $x[n]$ is actually a vector $\vec{x}$ in an $N$-Dimensional vector space. And, this $N$-D vector space has a set on $N$ Fourier Basis which reveals the frequency information of that $\vec{x}$. We know that projection of a vector onto another depends on dot-product (inner-product), $\langle\vec{x},\vec{y} \rangle$. The projection coefficient of a vector $\vec{x}$ onto a vector $\vec{y}$ :

$$P_{\vec{x}} = \frac{\langle\vec{x}, \vec{y}\rangle}{\langle\vec{y}, \vec{y}\rangle} = \frac{\sum^{N-1}_{n=0}x[n]y^{*}[n]}{\sum^{N-1}_{n=0}y[n]y^{*}[n]}$$
And, if we are projecting a vector $\vec{x}$ onto a unit length vector $\hat{y}$, then the Projection coefficient is exactly the dot-product, because, the denominator of the above expression will become 1.

$$P_{\vec{x}} = \langle\vec{x}, \hat{y}\rangle$$
That is exactly what the DFT Coefficient is. Projection Coefficient of time-domain sequence $\vec{x}$ onto $\vec{W_k^N}$
$$X[k] = \langle\vec{x}, \vec{W_{k}^{N}}\rangle = \sum^{N-1}_{n=0}x[n]\,W_k^{N}[n] = \sum^{N-1}_{n=0}x[n]e^{-j\frac{2\pi}{N} nk}$$

Now, notice that the $N$ Fourier Basis vectors are each at a digital frequency $\omega = \frac{2\pi}{N}k, k=0,1,2,...,N-1$. So, the DFT/FFT frequency bins just depend on the DFT Length and nothing else. DFT by itself is a perfectly fine operation on an $N$-dimensional vector. It is a linear transformation, just a change of basis from canonical basis set to Fourier Basis set, so as to reveal frequency information in that signal $\vec{x}$.

It reveals frequency information because projection(inner-product) of one vector onto another actually is a measure of similarity between the two vectors. So, each of the $X[k]$ is telling us how much similarity is between the time-domain sequence $\vec{x}$ and $k^{th}$ Fourier Basis, and, $k^{th}$ Fourier Basis is a sequence of digital frequency $\omega = \frac{2\pi}{N}k$. 

As I said, DFT by itself is perfectly fine operation on any vector of finite length. You do not have to link these digital frequencies with sampling frequency. But if you want to, then, it is enough to know that when we sample a signal at sampling frequency $f_s$, then the maximum frequency that can be represented in the sampled signal is $f_s/2$. And the maximum digital frequency is $\pi$. Hence, $f_s/2$ maps to $\pi$. And therefore the digital frequency of $k^{th}$ Fourier Basis, $\omega = \frac{2\pi}{N}k$ maps to $f = \frac{f_s}{N}k$.