This does not seem to be repeatable on Percona Server 5.5.28 when using default replication not the galera one.

Server version:         5.5.28-rel29.1-log Percona Server with XtraDB (GPL), Release rel29.1, Revision 334

-- master server:
master [localhost] {msandbox} (test) > show global variables like 'auto_increment%';
+--------------------------+-------+
| Variable_name            | Value |
+--------------------------+-------+
| auto_increment_increment | 2     |
| auto_increment_offset    | 1     |
+--------------------------+-------+
2 rows in set (0.00 sec)

master [localhost] {msandbox} (test) > select @@binlog_format;
+-----------------+
| @@binlog_format |
+-----------------+
| ROW             |
+-----------------+
1 row in set (0.00 sec)


-- slave server:
slave1 [localhost] {msandbox} (test) > show global variables like 'auto_increment%';
+--------------------------+-------+
| Variable_name            | Value |
+--------------------------+-------+
| auto_increment_increment | 2     |
| auto_increment_offset    | 2     |
+--------------------------+-------+
2 rows in set (0.00 sec)


-- test case run:

master [localhost] {msandbox} (test) > show tables;
Empty set (0.00 sec)

master [localhost] {msandbox} (test) > create table t (i int);
Query OK, 0 rows affected (0.14 sec)   

master [localhost] {msandbox} (test) > insert into t values (1),(2),(3),(4),(5);
Query OK, 5 rows affected (0.16 sec)   
Records: 5  Duplicates: 0  Warnings: 0 

master [localhost] {msandbox} (test) > ALTER TABLE `t` ADD `id` INT NOT NULL AUTO_INCREMENT PRIMARY KEY FIRST;
Query OK, 5 rows affected (1.18 sec)   
Records: 5  Duplicates: 0  Warnings: 0 

master [localhost] {msandbox} (test) > select * from t;
+----+------+
| id | i    |
+----+------+
|  1 |    1 |
|  3 |    2 |
|  5 |    3 |
|  7 |    4 |
|  9 |    5 |
+----+------+
5 rows in set (0.00 sec)

slave1 [localhost] {msandbox} (test) > select * from t;
+----+------+
| id | i    |
+----+------+
|  1 |    1 |
|  3 |    2 |
|  5 |    3 |
|  7 |    4 |
|  9 |    5 |
+----+------+
5 rows in set (0.00 sec)

And you can see that the AUTO_INC column has identical values.


The binary log contents on the master server are as follows:

*!40019 SET @@session.max_insert_delayed_threads=0*/;
/*!50003 SET @OLD_COMPLETION_TYPE=@@COMPLETION_TYPE,COMPLETION_TYPE=0*/;
DELIMITER /*!*/;
# at 4
#130124 10:20:58 server id 1  end_log_pos 107   Start: binlog v 4, server v 5.5.28-rel29.1-log created 130124 10:20:58
# Warning: this binlog is either in use or was not closed properly.
BINLOG '
+vwAUQ8BAAAAZwAAAGsAAAABAAQANS41LjI4LXJlbDI5LjEtbG9nAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAEzgNAAgAEgAEBAQEEgAAVAAEGggAAAAICAgCAA==
'/*!*/;
# at 107
#130124 10:21:08 server id 1  end_log_pos 215   Query   thread_id=2     exec_time=0     error_code=0
use test/*!*/;
SET TIMESTAMP=1359019268/*!*/;
SET @@session.pseudo_thread_id=2/*!*/;
SET @@session.foreign_key_checks=1, @@session.sql_auto_is_null=0, @@session.unique_checks=1, @@session.autocommit=1/*!*/;
SET @@session.sql_mode=0/*!*/;
SET @@session.auto_increment_increment=2, @@session.auto_increment_offset=1/*!*/;
/*!\C utf8 *//*!*/;
SET @@session.character_set_client=33,@@session.collation_connection=33,@@session.collation_server=8/*!*/;
SET @@session.lc_time_names=0/*!*/;
SET @@session.collation_database=DEFAULT/*!*/;
DROP TABLE `t` /* generated by server */
/*!*/;
# at 215
#130124 10:21:30 server id 1  end_log_pos 305   Query   thread_id=2     exec_time=1     error_code=0
SET TIMESTAMP=1359019290/*!*/;
create table t (i int)
/*!*/;
# at 305
#130124 10:21:35 server id 1  end_log_pos 378   Query   thread_id=2     exec_time=0     error_code=0
SET TIMESTAMP=1359019295/*!*/;
BEGIN
/*!*/;
# at 378
# at 418
#130124 10:21:35 server id 1  end_log_pos 418   Table_map: `test`.`t` mapped to number 36
#130124 10:21:35 server id 1  end_log_pos 472   Write_rows: table id 36 flags: STMT_END_F

BINLOG '
H/0AURMBAAAAKAAAAKIBAAAAACQAAAAAAAEABHRlc3QAAXQAAQMAAQ==
H/0AURcBAAAANgAAANgBAAAAACQAAAAAAAEAAf/+AQAAAP4CAAAA/gMAAAD+BAAAAP4FAAAA
'/*!*/;
### INSERT INTO test.t
### SET
###   @1=1 /* INT meta=0 nullable=1 is_null=0 */
### INSERT INTO test.t
### SET
###   @1=2 /* INT meta=0 nullable=1 is_null=0 */
### INSERT INTO test.t
### SET
###   @1=3 /* INT meta=0 nullable=1 is_null=0 */
### INSERT INTO test.t
### SET
###   @1=4 /* INT meta=0 nullable=1 is_null=0 */
### INSERT INTO test.t
### SET
###   @1=5 /* INT meta=0 nullable=1 is_null=0 */
# at 472
#130124 10:21:35 server id 1  end_log_pos 499   Xid = 21
COMMIT/*!*/;
# at 499
#130124 10:21:44 server id 1  end_log_pos 637   Query   thread_id=2     exec_time=1     error_code=0
SET TIMESTAMP=1359019304/*!*/;
ALTER TABLE `t` ADD `id` INT NOT NULL AUTO_INCREMENT PRIMARY KEY FIRST
/*!*/;
DELIMITER ;
# End of log file
ROLLBACK /* added by mysqlbinlog */;
/*!50003 SET COMPLETION_TYPE=@OLD_COMPLETION_TYPE*/;

The important thing to note is that the binary log sets the correct session variables first:
SET @@session.auto_increment_increment=2, @@session.auto_increment_offset=1/*!*/;

So when the slave thread replays the binary logs, the variables auto_increment_increment and auto_increment_offset for the slave thread match the values set on the master and hence the correct values are used during the ALTER.