That is not how I remember physics (former PhD student here):
The speed of light has a dimension, so it in itself does not change physics (thought experiment: everybody switches to feet-per-decade as the unit of choice, nothing really changes). It is the dimensionless constants that determine the real physics.
Have not heard the statement that is alpha was a tiny factor larger/smaller that would make atoms no longer exist. It's this were true, this would actually be a way to actually calculate it from first principles ('at which value of alpha are there solutions to this equation').
Edit: typo
There is the Hoyle state, a peculiar resonance state that is very important for nucleosynthesis. Without it, stars would not produce a lot of carbon. It appears to be finely tuned for complex chemistry and thus life to evolve.
The speed of light does change physics, as does any fundamental constant. Expressing a speed in different units does indeed yield different numbers, but that is not equivalent to a change of speed.
Changing alpha means that electromagnetic force get stronger or weaker, thus the atoms still exist but with different orbital levels. Considering how intricate the orbital levels of atoms are, it's not shocking that a tiny change in alpha completely redefines chemistry, but chemistry would still exist.
The point is that all of the speeds we measure are actually measured in units of the speed of light, if you go right down to it (seconds and meters are defined in terms of the speed of light). So, the value of the speed of light doesn't really matter - which is why c=1 is often used in many kinds of physics.
The fine structure constant is dimensionless and would be different if c were different. When doing a unit conversion, one also has to alter other constants so as to be consistent with observed reality; whether one alters other constants or not is the difference between talking about a change in units and a change in c.
It looks like this still doesn't cancel out? It's an interesting point as to whether our hypothetical change in c would affect the relationship between photon energy and wavelength, but either way we get a nonzero power of c.
Have not heard the statement that is alpha was a tiny factor larger/smaller that would make atoms no longer exist. It's this were true, this would actually be a way to actually calculate it from first principles ('at which value of alpha are there solutions to this equation'). Edit: typo