I believe your only options are Qantas, Jetstar and Hawaiian Airlines.
I flew Qantas in January, the planes they run are Boeing 767s, fitted out the same and with the same services that they use domestically. In fact, the plane I was on from MEL-SYD was the same one that flew us on from SYD-HNL. So basically there is no inflight entertainment. That cost 36000 points each way plus taxes for economy, would be 64000 business if you can get a seat. I have to say the seats in the plane were very old and shabby, so it wouldn't be the best use of points to pay for J on this leg in my opinion. However I understand your husband might need the extra leg room.
I can't comment on Jetstar's service, but I know Hawaiian Airlines will cost you 36000 points as well, available through Velocity. They run the 767s too I think, and I'm not sure their inflight service would be a whole lot better.
In any case, Hawaii is such a wonderful place I can assure you the flight will soon be forgotten :-)