We explore the possible effect of cluster environments on the structure and star formation histories of galaxies by analysing the projected phase-space (PPS) of intermediate-redshift clusters (0.4 <= z <= 0.8). HST I-band imaging data from the ESO Distant Cluster Survey (EDisCS) allow us to measure deviations of the galaxies' light distributions from symmetric and smooth profiles using two parameters, A(res) ('asymmetry') and RFF (residual flux fraction or 'roughness'). Combining these structural parameters with age-sensitive spectral indicators (H-delta A, H-gamma A, and D(n)4000), we establish that in all environments younger star-forming galaxies of all morphologies are 'rougher' and more asymmetric than older, more quiescent ones. Combining a subset of the EDisCS clusters, we construct a stacked PPS diagram and find a significant correlation between the position of the galaxies on the PPS and their stellar ages, irrespective of their morphology. We also observe an increasing fraction of galaxies with older stellar populations towards the cluster core, while the galaxies' structural parameters (A(res) and RFF) do not seem to segregate strongly with PPS. These results may imply that, under the possible influence of their immediate cluster environment, galaxies have their star formation suppressed earlier, while their structural transformation happens on a longer time-scale as they accumulate and age in the cluster cores.