Yes, Outsiders can polymorph into other Outsiders. The utility of this is mitigated by the fact that you get none of the Outsider's special abilities, so basically you're looking for an Outsider that has really good ability scores, and is humanoid--allowing you to continue using your equipment.
I played a tiefling rogue last year who had weapon finessed short swords. Unfortunately for her, nothing in the MM had a dex as high as she did, so she actually lost effectiveness even polymorphing into a celestial or fiend. But for a fighter, there are many celestials that are very nice for polymorph.
Keep in mind that a common house rule is that you must have actually encountered the creature before being polymorphed into it, though, so you'll have to meet up with the planetar before you can become one.