normally to provide a drive signal where the polarity can be reversed you would use a MOSFET H-bridge. Most examples you find online will show a motor at the center of the bridge, but you would just replace that with a solenoid.
Now, split the bridge apart, left and right, and you have a half-bridge.
Put one side on the rows, and the other side on the columns and drive it appropriately with logic signals.
To flip one way : logic LOW on the row, logic HIGH on the column.
Flip back the other way : logic HIGH on the row, logic LOW on the column.
There are half-bridge IC's and that can save you on parts count. I don't know if they make logic level half-bridge drivers. You'd have to search for such a part.
PS: since you are not doing PWM you probably won't need the TC4428 gate driver IC that is in the drawing I found on the web.