1) Anakin builds C-3PO. The history of his character remains the same as in the offical versions.
2) C-3PO is introduced in II at the Lars Homestead. His introductory dialogue is reworked. The big issue here would be explaining Anakin and Padme taking him with them when they leave.
3) C-3PO takes the place of TC-14 in I. We can explore various means of expanding his presence in the film. We'd have to make it evident he was left on the planet and given a memory wipe. These plotpoints could be dealt with in I or II, depending on what we can fit where with what dialogue. He remains Padme's servant in II and III; only a minor cameo would need to be worked into II. The droid at the Lars Homestead wouls be redubbed as a different droid.
3A) C-3PO takes the place of TC-14 in I. We can explore various means of expanding his presence in the film. We'd have to make it evident he was left on the planet and survied the end battle. When we get to the Lars Homestead in II, we can try to work in some exposition about how he came to be there. Or maybe we could leave it vague, with neither party know that 3PO was ever owned by the Trade Federation. When you can't explain it, leave it to the imaginiation. The issue would again arise, however, why do Anakin and Padme take him with them when they leave?
4) C-3PO is introduced in III as Padme's servant. He and R2 meet after the Invisible Hand rescue (Yoda Is Your Father's suggestion).
1 obviously would require the least work. 4 would take significant editing in I and II, but on the whole it wouldn't be too complicated. 2 would take some effort to explain why he leaves Tatooine (though this is never explained in the original, it is explained away as Anakin being his maker). Either 3 would require the most work, but would ultimately be the most rewarding if we could find a way to do it. These are out options gentlemen. What to do, what to do...