Your overall understanding is correct. Indeed, elements of a StorageVec are not consecutive and they live in persistent storage. The closest thing to storage in a computer is the hard drive actually. And yes, only contracts are allowed to use StorageVec while Vec is allowed in any program type.
StorageVec represent a mapping between the integers 0, 1, 2, … and storage slots, and those slots are not consecutive in the current implementation. The key for each of those slots is computed as the hash of some function of each integer.