Алексей Уколов

Категория, скорее всего, динамическая и зависит от товара. Если это так, то средствами nginx вы такой редирект не сможете сделать. Вам нужно все обращения на сайт/store/show/товар проксировать на специальный обработчик внутри вашего сайта, который уже будет определять по коду товара правильный адрес для редиректа и возвращать 301-й ответ.

Яндекс и Гугл по сути никак не отреагируют на 301 редирект, правильно?

Конечно, отреагируют, для этого редирект и делается в частности. Они будут выкидывать старые страницы из индекса и заменять их новыми (справка Google).

по каким данным (заголовкам)?

Ни по каким, вам нужно реализовать механизм аутентификации.

Вам нужно либо Haproxy, либо DNS load balancing, либо Elastic IP.
Эти инструменты решают разные задачи, поэтому выбирать нужно в зависимости от ваших реалий.

Как вариант давать юзеру "deployer" права через visudo и загонять в капистрано таск с коммандой по перезагрузке? Но правильно ли это будет с точки зрения безопасности?

На мой взгляд - нормальное решение. Только права давать исключительно на reload, но не на restart.

winginx.com/ru/htaccess