I read everywhere that the true altitude is computed as:
True Altitude = Indicated Altitude + (ISA Deviation × 4/1000 × Indicated Altitude)
But why is that the case? How is that derived? Where does that 4/1000 come from?
The exact formula to compute true altitude is:
$$h_{true} = h + \frac{h}{T_0}\cdot\left(T_\mathrm{OAT}-T_\mathrm{ISA}\right)\tag{1}$$
where you can see that the value usually represented by $\frac{4}{1000}$ is in fact $\frac{1}{T_0}=\frac{1}{288.15}\approx0.00347$. You can check how it's derived here
It isn't. Indicated altitude is a function of just the outside pressure and the altimeter setting. The pressure at a given absolute altitude is given by:
$$ P=P_0\exp\left(\int^{\rm altitude}_0-\frac{g}{R(h)T(h)}{\rm d}h\right) $$
where $P_0$ is the ground-level pressure, $R$ is the real gas constant for air (which depends on humidity) and $T$ is the at a given height AGL.
You don't have to evaluate this integral: the point here is that it depends on the temperature and humidity at every altitude between you and the ground. In other words, the relationship between pressure and absolute/true altitude depends on not only the local outside air temperature, but also the temperature lapse rate and the humidity at every level of the atmosphere below you.
The formula you've quoted is an approximation that works when the atmosphere is "kinda standard," i.e. when the temperature is non-standard but the temperature lapse rate and humidity are standard. It is done by evaluating an integral like this, given specific assumptions about the temperature profile, and then approximating the resultant equation as a straight line.
In short, it is impossible to compute your true or absolute altitude using only barometric information, outside air temperature, and altimeter setting. Having an altimeter setting and temperature as measured at a nearby airport helps a lot, but it isn't sufficient to determine the true altitude unless your plane is sitting on the ground at said airport.