Find Antony and agree to fight a few of his dogs in the Legion arena in exchange for the bear. This can be avoided if you have good reputation with the Legion. You may also pickpocket the bear from Antony or kill him for it. Alternatively:
If you have the Animal Friend perk you can make Antony give you the bear straight away, although he will comment that it's "no fun".
If you have a 50+ Barter skill, noticing that he risks losing many good hound in a fight will persuade him to put two dogs against you, instead of four.
Xbox 360 If you start a fight at the fort, occasionally Melody will flee to the fort's entrance. Along with all other characters, she can clip through the other side of the gate. The other side of the gate is in the same cell as the Fort's interior and the blip will appear on the compass. While an npc is there you can see them by looking through two holes in the walls on either side of the gate. [verified]
Xbox 360 To fix this jump on the boxes next to Antony and Lupa (if still alive), then on two wall parts on the right, and try to jump over the wall. After that go to drawbridge gate, jump on the wall parts to pass through the rock. Use 3rd person camera to use drawbridge gate, so you'll enter Caesar's part of the Fort again (you are there already). Now Melody should be in the brahmin pen.
PC The dialogue option to end the conversation with Melody may not be present, forcing the player to revert to a previous save and rendering the quest unobtainable.
PC If you have ED-E as an active companion he may actually aid you in a fight, although arena fight is supposed to be a "one vs many" combat.