add column without metadata lock in mysql 5.6
I have executed the very same query on 5.6.14 and got a positive result:

alter table candidate_candidate add column responsible_user_id int, algorithm=INPLACE, lock=NONE;
Query OK, 0 rows affected (0.48 sec)
Records: 0  Duplicates: 0  Warnings: 0


So I am sure that this kind of operation can be done online. You are probably experiencing some of the exceptions shown at: http://dev.mysql.com/doc/refman/5.6/en/innodb-create-index-limitations.html

My bet would be on having outdated temporal datatypes, foreign keys or fulltext indexes. Any of those on the table? Recently migrated from 5.5? If I am wrong, can you show the full CREATE TABLE?