Driving both the row and column string at the same time cuts the total update time in half. Each string still needs 128 (or 64) clock and data bits.
Like BB said, the current is the real question. Even with a low voltage, a short piece of wire can draw several amps, due to its low resistance. And, if you were testing with a AA battery, the actual voltage delivered from the battery during the test will have been lower than the 1.2 open circuit volts. Probably significantly lower due to the internal resistance of the AA battery.
For an electromagnet, magnetic strength is a function of AmpTurns. A coil of 1 turn drawing one amp will have the same magnetic strength as a coil of 10 turns drawing 0.1 amps. The reason most electromagnets, such as solenoids and relays, have many turns, is to use as little current as possible while still having sufficient magnetic strength to get the work done.
In your case, the ideal coil will be optimized to run at ~5 volts. Design your coil with however many turns gives you the strength you need, while drawing as little current as possible. Only when you get to that point will you know whether you can drive the coil directly from whatever logic you choose, or if you need to buffer the logic outputs with transistors.
Notes:
- The current in a DC coil will be a controlled by it's resistance and the applied voltage as per Ohms Law.
- You can run your logic circuits at a voltage lower than 5V. This will mean fewer turns in your coils to still be optimized for the working voltage. 3.3 Volts is a common level, but the HC595 claims to be usable down to 2V.
- While resistance is the dominant factor for DC current, if you are driving the coils with short pulses, the inductance of the coils may also be a factor in limiting the current.