To start with work as many hills as you can, that's part of how I started my mare back to work too (during good weather that is). The team penning really would have given him incorrect gaited horse muscle memory. It's perfectly fine to use gaited horses for anything you want to do, once you develop proper muscle memory for the gait. It probably was not properly developed in him from the beginning by the look of his topline, or if it was he lost it in being used for other things without it being "set" so to speak. It will take a little time and effort now, but you can do it. You can ALWAYS make it better, no matter what someone says! And good for you for working on it with him! It will actually help keep him sound long term to do it properly.
On the hill work let him do the gait but hold him in (with two hands on gentle contact) and dont let him go faster, even relatively steep hills, it will build his back muscle. Start off with a few for now and work up to it.
I will try not to write a book but on paper it always takes longer to explain something than in person! LOL.
In the arena you want to ride him with 2 hands on light contact. To start with hold your hands a little up in the air and rather far apart, to help him learn the head carriage (it looks funny but it works). I never crank on my mare's mouth, but to help him you will need to "support" him in the proper frame for now. Light constant contact with a little more pressure as needed to get his neck up. He should have his neck up, not like a quarter horse, and nose just in front of vertical. That's where you want to end up. Of course he probably won't start there, work on just getting his neck up for now, can work more on his proper head carriage later. Sometimes they will nose out to start with, but give a little more contact to help bring his nose in (eventually). This will free up his shoulders (by bringing his head up and out of the way) to allow him to reach forward with his front legs. That will open up his front stride and allow him to reach forward from the shoulder more effectively. Encourge him forward as fast as he can go at the flat walk without breaking into the pacey jog. At first this will not be very fast before he breaks (their backs have to build back up from the incorrect way of going so it takes time). When he breaks, gently bring him back down and start over. You will keep light contact at all times and hands apart and up in the air a little for now. That's where you start, and with the hill work as much as you can.
Eventually his speed will pick up at the flat walk as he builds muscle (you will see his topline change and start to build muscle down the spine and hip area). His pacing jog is easier than gaiting for him but that will change. You will feel it when he hits a 4 beat, and his head bob will be more pronounced. Don't get frustrated, at first you may only get a few steps on gait before he breaks, but keep trying you will get there!
Start there and let me know how it goes. This takes several months, but you will see him gradually gain strength and improve his movement.
I will try to get some before and after videos of my mare for you to see the difference, and maybe I can show you exactly what I mean with hand position etc. I have some before where she was pacey and a mess but no after videos right now.