Reading your original post again, I still don't really understand all your questions and doubts, or why you believe transistors would be needed. So I will just describe how I would approach it and perhaps you will point out to me what i am missing.
You have an Arduino Mega, so plenty of outputs. Connect 13 outputs to the note connectors and another 5 to the NO octave connectors. Leave the NC connections unconnected. Also connect 13 10K resistors from the note connectors to ground.
Your sketch would then set all 5 of the octave outputs to ouput mode and low. The 13 note outputs woul be in input mode. For each octave output in turn, set that output to high and read the 13 inputs. Then set the octave output back to low and move to the next octave output and so on.