Wow, I would have thought that he would have explained the situation and cleared it with you before doing any work on that toilet rough-in. I can't say whether the install was done incorrectly without seeing pictures because maybe he was telling the truth that he could not install on the other side of the joist without destroying it. The only thing that comes to mind is to use a toilet that utilises a uni-fit rough-in flange that would take off 2 inches...but you would still be stuck with a 4 inch gap...which is pretty ugly. Maybe build some shelving around the toilet tank and hide the gap?
Anyone else got any ideas?