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 (> 1E+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. 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. H.E.S.S., with its large field of view, angular resolution of < 0.1deg 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 (-80deg < l < 60deg, |b| < 3deg), together with the existing multi-wavelength observations, are used. A new VHE gamma-ray source was discovered at R.A. (J2000) = 13h56m00s, Dec. (J2000) = -64d30m00s 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)deg. Its integrated energy flux between 1 and 10 TeV of 8E-12 erg cm-2 s-1 represents ~ 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 ~ E-Gamma with photon index Gamma = 2.2 +/- 0.2stat +/- 0.2sys. 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. HESS J1356-645 is most likely associated with the young and energetic pulsar PSR J1357-6429 (Abridged)