Is this legit? I fire my hired gun, play the By Any Means Necessary card to fire again, recieve the four damage, then attack again with parting blow?

Yup. Hired Gun attacks, triggers By Any Means Necessary, gets a second attack against the same target, and then takes 4 damage. If the Hired Gun is then defeated by this damage, Parting Shot triggers a third attack.

Necroing this thread because there was a similar question in the slack the other day, but in reverse order. Hired Gun or Greedo uses Parting Shot, can they then use the previously mentioned agenda card to perform an additional attack before they are defeated by Parting Shot? The agenda card is "use after a mercenary figure resolves an attack" and doesn't use the word "interrupt". Parting Shot says "Perform an attack. Then you are defeated."

Yes.

("Interrupt" is mostly superfluous and used for emphasis. You have "perform an attack" with a mercenary affiliation figure, so the agenda card can be played.)