Which principle would be violated?

It would violate common formulations of the Einstein Equivalence Principle, one part of which is:

"The outcome of any local non-gravitational experiment is independent of where and when in the universe it is performed."

See, for example, section 2.1 of:

http://relativity.livingreviews.org/Articles/lrr-2006-3/ [Broken]

However, this principle is more involved in motivating GR, than functioning as a strict consequence, given the equations of GR.

So a different question would be, could a theory of varying alpha be consistent with GR? I am not sure that is so difficult. One could imagine some field permeating the universe, following a covariant law, that influences alpha.

In any case, I think GR would not be the only major modern theory affected by varying alpha. I think it makes the article more exciting to specifically mention GR.