Replace chip (PCB) in usb midi keyboard with arduino

OK that is fine as long as those are your expectations.
The most common way for a velocity sensitive keyboard is to have two switch contacts per key. When a key is pressed first one contact is broken and then the other one is made. The time between make and break is the velocity data.

The complication arises because you are trying to measure the time of multiple contact changes at the same time.