A new dynamic melting state, which has both solid and liquid characteristics, is revealed from first-principles molecular dynamics simulations of Al-55 clusters. In thermal fluctuations near the melting point, the low-energy tetrahedral-like Al-55 survives through rapid, collective surface transformations-such as parity conversions and correlated diffusion of two distant vacancies-without losing its structural orders. The emergence of the collective motions is solely due to efficient thermal excitation of soft phonon modes at nanoscale. A series of spontaneous surface reconfigurations result in a mixture or effective flow of surface atoms as is random color shuffling of a Rubik's cube. This novel flexible solid state (termed as half-solidity) provides useful insights into understanding stability, flexibility, and functionality of nanosystems near or below melting temperatures.