How did he come up with this idea before there was any experimental data to prove this?
See ON THE ELECTRODYNAMICS OF MOVING BODIES, by A. Einstein, where he explains the prior experimental evidence, and then shows the logic for Special Relativity. He was not the first to show the relative timekeeping of moving clocks, this was already known from the analysis of the Michelson-Morley experiments.
Einstein recognized early on that gravitation was inconsistent with Special Relativity, and sought new principles, including the Equivalence Principle. By applying this to his "Elevator" thought experiment, he was able to predict the gravitational red shift.
Ultimately, he used prior experimental results plus Maxwell's equations, and sought for logical, self-consistent theory with predictive power.
That time is affected by speed was suggested before Einstein by Larmor, and was motivated by experimental data, namely the Michelson-Morley (later also Trouton-Noble) experiments to detect the ether wind. As for gravity its influence on matter came out of general relativity as a side effect, its development was driven by different issues: equivalence of inertial and gravitational masses and the Mach's principle, which led to the general covariance requirements (equivalence of all frames, inertial or not) philosophically, and the perihelion of Mercury experimentally, see Why did Einstein develop General Relativity?
To explain the negative result of the experiments Fitzgerald in 1889 and Lorentz in 1892 introduced the length contraction for moving objects. But as Larmor pointed out in 1897 the length contraction by itself was not enough to explain the effect, the time had to be dilated as well. Larmor then showed that if the intermolecular forces were of electromagnetic origin obeying the Maxwell electrodynamics then length contraction and time dilation (as measured by devices so composed) will follow. As we would now say this is because the Maxwell electrodynamics is invariant under the Lorentz transformations, which Larmor also introduced in 1897, two years ahead of Lorentz. He presented his theory systematically in his book Aether and Matter (1900).
Of course, to Fitzgerald, Lorentz and Larmor contraction and dilation were just apparent effects caused by dynamics of clocks and rulers that in no way affected the "true" absolute time and absolute space. In turn, Einstein's insight was that it is the "apparent" effects that were the physical ones, and the ether with the absolute space and time attached to it were the unphysical. Einstein therefore "transformed" the time dilation effect from illusion to reality, and from dynamic to kinematic and universal (not just affecting electromagnetic phenomena), rather than came up with it. Perhaps unsurprisingly, Lorentz and Larmor (and even Poincare) rejected Einstein's re-interpretation, they saw no need to abandon their old school theories on the basis of experiments they already explained.