Adding Ground Conductor from Service to Upgraded Sub-Panel
I quite agree, pulling three 4/0 Al wires is the kind of job a DIYer ends up getting stuck on and having to call an electrician just for his truck full of pulling tools. 

How old is this work?  If it was legal to wire ungrounded at the time, it may be legal to retrofit ground using the NEC rules allowed for that.     For a retrofit, the rules are liberalized and you have a much wider set of choices for how to get it done.  Make that argument to the AHJ and see what they say.  

Also, why dig a wnole 'nother trench? You only need to dig out the old trench to the 45, which I assume is only a few feet from the house and shed.  Then you can disconnect the wires, cut the pipe (carefully) and get the access you need to get the ground wire through.  If the joints were not cemented, it'd be even easier.   Really keeping an underground conduit watertight is a lost cause, it will fill up with water, that's why the wire has a THWN rating.  So not cementing it does make sense.  It's exactly what I'd do in that circumstance.  

Also, if your wire is the obsolete AA-1350 type, just be careful with your terminations, make sure the lugs are made of aluminum (most are), use the anti-ox and torque them exactly to spec.  I see no reason to spend a fortune on new AA-8000 wire, they both conduct electricity just fine, the issue was always at the terminations, and even that was mainly an issue for the tiny wires (10-12 AWG) on Cu terminations.  On the other hand if the old wire is not outdoor rated, that's a different kettle of fish.