Suppose we have a mass $m$ in space, and we then introduce a bigger mass $M$. both have no kinetic energy initially.
$M$ & $m$ attract, and move towards each other gaining some kinetic energies along the way. At this point in time, the overall energy of the system isn't 0.
Since Law of conservation of energy will always hold up, there is obviously some flaw here that I've overlooked.
What is that flaw?
You have overlooked the existence of potential energy. The total energy is
$$E = \frac12 m v^2 + \frac12 M V^2 - G \frac{m M}{d},$$
where $d$ is the distance between the two masses, and it is indeed constant. In mechanics, the law of conservation of energy comes from the work-energy theorem, which doesn't say that kinetic energy is constant: it says that the change in kinetic energy is equal to the work done by all the forces,
$$\Delta T = W = \int \mathbf{F} \cdot d\mathbf{r}.$$
If the force is conservative, as gravity is, then the work done is by definition equal to minus the change in potential energy:
$$W = - \Delta U,$$
and thus $\Delta T + \Delta U = 0$, which means that the total energy $E = T+U$ is constant.
Initially both the bodies would have gravitational potential energy associated with them. As they move towards each other some of it will be converted into kinetic energy but at every point total energy will be the same as initially was.
