Your third example is grammatical but clumsy, the other three are wrong. (3) would read better if you substituted had for got.
Having had his car washed, Tim didn't pay me.
This implies both that you washed the car and that Tim had agreed to pay you but doesn't make it clear. To make it clear, you might write:
Having had his car washed by me, Tim didn't pay me as he had agreed.
That's a bit of a mouthful and would be better written as:
Tim failed to pay me for washing his car as he had agreed.
(although both those examples are slightly ambiguous and the second example loses the participle introduction!)
The rule when you introduce a sentence with a participle is to follow it with the correct subject. Failure to do so leads to confusing sentences like these:
Having robbed the shop, the policeman arrested the thief.
So reconsidering your other sentences:
(1) is wrong because Tim didn't wash the car, you did.
(2) is wrong because when you say: *I having washed his car, * you have to continue the sentence with what you did, not what Tim did.
(4) is wrong because the phrase having me wash his car has to act as the subject of a sentence, as in: Having me wash his car was Tim's birthday wish