Impact of switching a column's encoding from utf8 to utf8mb4 in MySQL
First, a syntax error:  it's MODIFY, not CHANGE, unless you are changing the column name, too.

I ran an experiment with only 1/2 million rows.  ALTER to change one column from utf8 to utf8mb4 took 1.6 seconds.  I conclude that the table was copied over; that is O(n).

When the developers added the various speedups for ALTER, I suspect they overlooked the case of utf8->utf8mb4, or decided that it was a risky special case -- what if later the charsets diverged?  Or the collations diverged?  Granted, without any index on the column, that should not matter.  (But that would be more more thing to test for before doing the Alter some faster way.)