Altering a table to add a New Column vs Create table with New Column
This is a question which gets asked regularly in some form or other here. Take a look at my reply to a similar one not so long ago.

Basically, there are two main tools out there for this - either Percona's pt-online-schema-change (available here) or Shlomi Noach's oak-online-alter-table (from here).

There are a couple of other possible solutions mentioned which may or may not be more applicable to Windows (you didn't mention your OS) but you do specifically mention MySQL 5.5 which appears to preclude this (unless Percona have back-ported it?). 

The usual disclaimers apply - about testing before implementing in production.

[EDIT - in response to OP's comment]

With replication, the situation is, apparently, the following (from here).


  REPLICATION
  
  If you use pt-online-schema-change to alter a table on a server with
  slaves, be aware that:

The tool is not tested with replication
The tool can break replication if not used properly
Although the tool sets SQL_BIN_LOG=0 by default (unless --bin-log is specified), triggers which track changes to the table being altered
still write statements to the binary log
Replicaiton will break if you alter a table on a master that does not exist on a slave
Update slaves first if columns are being added or removed
Do not use this tool in production before testing it



So, not exactly confidence inspiring, but not a total no-no either. Just follow the recommendations and test on a non-production machine.

Another possibility would be to use the relatively new online DDL capacity introducted in MySQL 5.6. From here, check a report of someone who tried to use Percona 5.6's online DDL - but, they apparently didn't apply changes to slaves before masters. All I can say is follow the instructions, test and see how it goes, whatever method you eventually decide on.

Did you check out the table here (from my original post to which I referred you)? It appears to be very similar situation to yours - add a column to a table with ~1,100,000 records - no locking, done in 30 seconds with pt-online-schema-change? Might be good for you? :-)