You'd think that people would be giving away UST lightweight 26" cross country wheelsets, and I could just bin the rear, ditch the front and upgrade for cheaps, but no, and I think you are probably right in that there's no easy solution so a new hub + spokes it probably is.
Measure the pcd but I think your best bet is a novatec d712 hub and new spokes.