Правильно: Ходатайствую о награждении Стрелец Татьяны Ивановны почётной грамотой.
Возможны варианты: Стрельца и Стрелеца.
Да, склоняются все мужские фамилии, оканчивающиеся на согласный (за исключением фамилий на -ых типа Черных). Мужская фамилия Стрелец склоняется.
Грамматически верное сочетание: не верьте в трех человек. Однако данное предложение составлено некорректно, его следует перестроить, например: Никогда не верьте людям трех знаков зодиака: Стрельцам, Овнам, Рыбам.