With the popularity of GPS-enabled devices, a huge amount of trajectory data has been continuously collected and a variety of location-based services have been developed that greatly benefit our daily life. However, the released trajectories also bring severe concern about personal privacy, and several recent studies have demonstrated the existence of personally-identifying information in spatial trajectories. Trajectory anonymization is nontrivial due to the trade-off between privacy protection and utility preservation. Furthermore, recovery attack has not been well studied in the current literature. To tackle these issues, we propose a frequency-based randomization model with a rigorous differential privacy guarantee for trajectory data publishing. In particular, we introduce two randomized mechanisms to perturb the local/global frequency distributions of significantly important locations in trajectories by injecting Laplace noise. We design a hierarchical indexing along with a novel search algorithm to support efficient trajectory modification, ensuring the modified trajectories satisfy the perturbed distributions without compromising privacy guarantee or data utility. Extensive experiments on a real-world trajectory dataset verify the effectiveness of our approaches in resisting individual re-identification and recovery attacks and meanwhile preserving desirable data utility as well as the feasibility in practice.