As rs.29 points out in the comments, C-3PO was originally a fully functioning protocol droid that really did work as a programmer of binary load lifters before he was deposited into a junkyard on Tatooine and rebuilt by Anakin Skywalker.
The rebels simply wiped only the parts of his memory relating to their location, leaving his earlier life, including his previous jobs, intact.
C-3PO had his memory wiped more than once, but most importantly he had his memory wiped whilst aboard the Tantive IV to remove any information he had about the rebellion, before being dumped on Tatooine.
This "job" that he believes to have had is almost certainly a false memory, given that we know he was built by Anakin Skywalker and has never had a real job.
Bonus Out-of-Universe answer: It's his genuine backstory at the time. Memory wipes can selectively remove specific pieces of information, and so the rebels only removed anything regarding their whereabouts. When the original Star Wars came out, they weren't even certain that they'd get enough money to make one sequel, let alone a saga including prequels. At a later time, Threepio as a character was incorporated into the story via Anakin in A Phantom Menace, but when the original Star Wars came out, they didn't have to worry about such continuity, so it's largely a throw-away line.