The way I see it would be to have 3PO being the property of Cleig Lars in Episode 1. 3PO and R2 could meet in the pit areas of the Boonta Eve race. He'd get introduced to Anakin in there somewhere, and they remember each other in Episode 2. This seems to be the simplest solution, it eliminates the "problem" of Anakin creating 3PO and doesn't make any editing and re-writing any harder than it needs to be.
-TheSluggo