I am a little confused about your described hand action. The fact that you use A, B, and C to denote players implies to me that they're acting in that alphabetical order. If A bets 1000 and B calls 1000, then C calls all-in for 500, there's no reason for A to fold, because he owes no additional money to stay in the hand. Can you please clarify that action?
In general, if there is a side pot (as in this hand, where there would be 500 from each of A and B on the side for a total of 1000), the last player remaining in the hand who is eligible for that side pot will win the side pot. So, if A and B remain in the hand (with C already all-in) and A bets and B folds, A will immediately win the side pot. If B mucks his hand for whatever reason, the side pot would be awarded to A, given that A now has the only live hand that's eligible for the side pot. The hand will then play out between A and C and the best hand between A and C will win the main pot.
Also, to remark on your question title... there is always an eligible winner, and that winner is either the side pot participant who has the best hand at showdown, or it's the player who held the last live side pot-eligible hand.