Aims. Hundreds of giant planets have been discovered so far and the quest of exo-Earths in giant planet systems has become intriguing. In this work, we aim to address the question of the possible long-term coexistence of a terrestrial companion on an orbit interior to a giant planet, and explore the extent of the stability regions for both non-resonant and resonant configurations. Methods. Our study focuses on the restricted three-body problem, where an inner terrestrial planet (massless body) moves under the gravitational attraction of a star and an outer massive planet on a circular or elliptic orbit. Using the detrended fast Lyapunov indicator as a chaotic indicator, we constructed maps of dynamical stability by varying both the eccentricity of the outer giant planet and the semi-major axis of the inner terrestrial planet, and identify the boundaries of the stability domains. Guided by the computation of families of periodic orbits, the phase space is unravelled by meticulously chosen stable periodic orbits, which buttress the stability domains. Results. We provide all possible stability domains for coplanar symmetric configurations and show that a terrestrial planet, either in mean-motion resonance or not, can coexist with a giant planet, when the latter moves on either a circular or an (even highly) eccentric orbit. New families of symmetric and asymmetric periodic orbits are presented for the 2/1 resonance. It is shown that an inner terrestrial planet can survive long time spans with a giant eccentric outer planet on resonant symmetric orbits, even when both orbits are highly eccentric. For 22 detected single-planet systems consisting of a giant planet with high eccentricity, we discuss the possible existence of a terrestrial planet. This study is particularly suitable for the research of companions among the detected systems with giant planets, and could assist with refining observational data.