How prevalent is Taq polymerase in adding 3' A overhangs to the PCR product?
I am not sure of a case where Taq doesn't add 3' A overhangs.  

You could use TA cloning to clone your PCR product.  The basic principle is to use a vector with 3' T overhangs.  If you have a vector without these overhangs, you can use a terminal transferase + dTTPs to create them (or even Taq, but this is not as great because it adds a purification step to isolate the vectors with overhangs; terminal transferase is much more efficient).  You can then ligate your PCR product that has a 3' overhang.

Protocols for adding the 3' T overhangs to your vector are given in Zhou and Gomez-Sanchez 2000.