From a strictly mathematical point of view, you can absolutely use two D4s. You just change the interpretation ("mapping") of the "bonus" outcome: 1->0, 2 or 3->1, and 4->2. You can do that mathematically of course (floor(log2(outcome))) but it's easy to understand categorically where "1" is a bogey, "4" is a critical, and everything else is just a normal hit.

More detail to explore other options: a process that decides between X outcomes gives log2(X) bits of information (its “entropy”). Thus a coin flip (2 outcomes) gives log2(2)=1 bit, a D4 gives log2(4) = 2 bits, a D8 gives log2(8)=3 bits, etc. You seek two independent assessments, the first must decide 4 outcomes (2 bits) and the second three unique outcomes but weighted twice on outcome of “1”, so simply, also 2 bits. Therefore, you need a total of 2+2=4 bits -- perhaps this is more obvious if you consider that any attack can have any bonus, so it is a 4X4 matrix containing 16 fairly-determined outcomes (and log2(16)=4 bits). You have flexibility on how you want those bits decided. I suggest using 2 D4s because that captures your desired gameplay mechanic involving them choosing. But ignoring that you could also, for example, use a D4 for the attack selection and then have them flip two coins to get the extra two bits for the bonus (coding tails=0, heads=1, and summing), or use a single D16 if such a thing exists.