How does Brimaz work with Frontline Medic? Will the battalion trigger due to brimaz putting a token into play attacking when brimaz attacks? If so this makes the medic a must have card with Brimaz
It will not. Triggered abilities don't actually take effect until after attackers have been declared, and Frontline Medic only checks to see if two other creatures are attacking at the very moment that it's declared as an attacker. Brimaz will still be the only other creature attacking at that point.
Battalion cares about how many creatures attack (that means "are declared as attackers in the beginning of declare attackers step"). Brimaz's cat soldier token is a creature that entered the battlefield already attacking but never attacked ( = wasn't declared as an attacker), so they don't count for Battalion.
EDIT: On the other hand, if you have Brimaz, Medic and a third creature (maybe a token created in a previous combat), and you attack with those three, both Brimaz's ability and Medic's battalion trigger at the same time, so you can order them to have the new token be created first, and then make it indestructible with Medic's battalion.
EDIT: On the other hand, if you have Brimaz, Medic and a third creature (maybe a token created in a previous combat), and you attack with those three, both Brimaz's ability and Medic's battalion trigger at the same time, so you can order them to have the new token be created first, and then make it indestructible with Medic's battalion.