Author here. The table did actually have a primary key, during the migration it was changed to unique, and then the new auto-incremental primary key was added.

I've updated the article to make that part clear.

I agree that having the binlog_format to ROW is the only option that make sense, which thankfully seems to be the default now.

That makes sense then.

If the table had a primary key, in case you ever face such a setup again (hopefully not!) then I think pt-online-schema-change to add the auto increment primary key while using ROW would probably be a better choice than the steps I mentioned in my first reply. It will rebuild the table anyway but at least it won’t block it while that happens.