We report Te-125 nuclear magnetic resonance and Ta-181 nuclear quadrupole resonance studies on single-crystal Ta4Pd3Te16, which has a quasi-one-dimensional structure and superconducts below T-c = 4.3 K. Ta-181 with spin I = 7/2 is sensitive to quadrupole interactions, while Te-125 with spin I = 1/2 can only relax by magnetic interactions. By comparing the spin-lattice relaxation rate (1/T-1) of Ta-181 and Te-125, we found that electric-field-gradient (EFG) fluctuations develop below 80 K. The EFG fluctuations are enhanced with decreasing temperature due to the fluctuations of a charge densitywave that sets in at T-CDW = 20 K, below which the spectra are broadened and 1/T1T drops sharply. In the superconducting state, 1/T-1 shows a Hebel-Slichter coherence peak just below Tc for Te-125, indicating that Ta4Pd3Te16 is a full-gap superconductor without nodes in the gap function. The coherence peak is absent in the 1/T-1 of Ta-181 due to the strong EFG fluctuations.