Recurrent Neural Networks (RNNs) and Long Short-Term Memory (LSTM) networks are utilized to capture the dynamic trends of 15 environmental parameters including particulate matter and pollutants in the atmosphere that cause long-term health hazards. Despite having the capability for capturing the long-term dependencies and nonlinearities in dynamic data, these deep learning based models suffer from overfitting if hyper-parameters are not determined optimally. For this purpose, a novel evolutionary algorithm for neural architecture search balancing the accuracy-complexity trade-off through a multi-objective optimization is proposed. This algorithm not only designs optimal deep-RNNs, but also ensures simultaneous determination of activation function and truncated backpropagation length. Analysis of many-to-one and many-to-many styled RNNs concluded that latter style is more effective. Subsequently it is compared with that of LSTMs to achieve an overall accuracy between 85.612% and 99.56%. To further minimize this error, multi-variate modelling is proposed. However, since it is important to identify the most significant features, which can be considered as inputs to multi-variate deep RNNs, Monte Carlo based Global Sensitivity Analysis is performed. It proved the hypothesis with sufficient statistical evidence that pH of rain (whose univariate modelling accuracy was least among all) is affected by methane, carbon monoxide, non-methane hydrocarbons and total hydrocarbons, thus improving the modelling accuracy to 98.97%. These models not only can help policymakers make informed decisions and mitigate climate change, but also the approach can be extended for other time-series modelling related applications due to its generic nature. © 2021 Elsevier B.V.