What is wrong with driving the columns of your matrix with a high side P_FET and driving the rows with a low side N_FET? You will need some level translation circuitry to high side drive your PFET (and possibly another opto coupler). It would be an EMC nightmare, but structurally it looks quite straight forward.
I also notice you have no back emf diode across your solenoid.
The sneak path through L3 will energize M5, which will drive L2 and L5 in series, plus L1 and L4 in series.To switch on L6, drive M8 and M4.
..The path through L5 will energize M4, and drive L3 and L6 in series plus L3 and L4 in series.To drive L2, drive M7 and M5.
The sneak path through L3 will energize M5, which will drive L2 and L5 in series, plus L1 and L4 in series.