You do not need a logic-level FET for the P-channel ones because their gate voltage will swing from 0V to 12V. You do not need logic-level FET's for the N-channel ones either if you are going to use a gate driver like the TC4428.
I would keep the TC4428 (or similar) gate driver because FET's with high current handling and low on-resistance will generally have large gate capacitance, which is difficult to drive from a microcontroller and can even damage it over time due to high peak currents.
VDD for the TC4428 should be 12V, not 5V.
I would recommend pull-down resistors at the inputs of the TC4428. In case the Arduino outputs float, you don't want both TC4428 outputs turning on at the same time (that will destroy your MOSFET's very quickly).
There should be a capacitor close to the TC4428 (1uF ceramic or so). A "big" capacitor for the motors....that is less well determined. Some capacitance definitely helps, but I don't know of a definite sizing guide. I generally throw something like 220uF-330uF there.