Context. Several newly discovered very-high-energy (VHE; E > 100 GeV) gamma-ray sources in the Galaxy are thought to be associated with energetic pulsars. Among them, middle-aged (greater than or similar to 10(4) yr) systems exhibit large centre-filled VHE nebulae, offset from the pulsar position, which result from the complex relationship between the pulsar wind and the surrounding medium, and reflect the past evolution of the pulsar. Aims. Imaging Atmospheric Cherenkov Telescopes (IACTs) have been successful in revealing extended emission from these sources in the VHE regime. Together with radio and X-ray observations, this observational window allows one to probe the energetics and magnetic field inside these large-scale nebulae. Methods. H.E.S.S., with its large field of view, angular resolution of less than or similar to 0.1 degrees and unprecedented sensitivity, has been used to discover a large population of such VHE sources. In this paper, the H. E. S. S. data from the continuation of the Galactic Plane Survey (-80 degrees < l < 60 degrees, vertical bar b vertical bar < 3 degrees), together with the existing multi-wavelength observations, are used. Results. A new VHE gamma-ray source was discovered at RA (J2000) = 13(h)56(m)00(s), Dec (J2000) = -64 degrees 30'00 '' with a 2' statistical error in each coordinate, namely HESS J1356-645. The source is extended, with an intrinsic Gaussian width of (0.20 +/- 0.02)degrees. Its integrated energy flux between 1 and 10 TeV of 8 x 10(-12) erg cm(-2) s(-1) represents similar to 11% of the Crab Nebula flux in the same energy band. The energy spectrum between 1 and 20 TeV is well described by a power law dN/dE proportional to E-Gamma with photon index Gamma = 2.2 +/- 0.2(stat) +/- 0.2(sys). The inspection of archival radio images at three frequencies and the analysis of X-ray data from ROSAT/PSPC and XMM-Newton/MOS reveal the presence of faint non-thermal diffuse emission coincident with HESS J1356-645. Conclusions. HESS J1356-645 is most likely associated with the young and energetic pulsar PSR J1357-6429 (d = 2.4 kpc, tau(c) = 7.3 kyr and (E) over dot = 3.1 x 10(36) erg s(-1)), located at a projected distance of similar to 5 pc from the centroid of the VHE emission. HESS J1356-645 and its radio and X-ray counterparts would thus represent the nebula resulting from the past history of the PSR J1357-6429 wind. In a simple one-zone model, constraints on the magnetic field strength in the nebula are obtained from the flux of the faint and extended X-ray emission detected with ROSAT and XMM-Newton. Fermi-LAT upper limits in the high-energy ( HE; 0.1-100 GeV) domain are also used to constrain the parent electron spectrum. From the low magnetic field value inferred from this approach (similar to 3-4 mu G), HESS J1356-645 is thought to share many similarities with other known gamma-ray emitting nebulae, such as Vela X, as it exhibits a large-scale nebula seen in radio, X-rays and VHE gamma-rays.