Example: I initiate a military challenge with 1 character with deadly and he defends with 1 character without deadly and I win the challenge. Can he claim the character who was involved in the military challenge as his claim or does deadly kill that character first and then he must claim a different character for claim?

For a more complete answer, check the timing chart in the FAQ.

Short answer:
Claim happens first (followed by awarding renown), then followed by all other passives (including deadly). If any passives conflict, they are resolved in the order determined by the first player. In this case, if he chooses his defender to die to claim, there'll be no one left to die to deadly.

From the FAQ:

When do you resolve deadly?

Deadly is resolved during the passive resolution step in the Framework Action Window.

Also from the FAQ:

Framework Actions

A. Determine Winner

B. Implement Result (Claim)

C. Reward for Unopposed

D. Renown

E. Passive Effects

F. Responses

So claim first, then deadly .