A VAO is purely a software/driver-side construct designed to manage state changes, and doesn't have much parallel in hardware, so whether or not a VAO is used is largely irrelevant in the case of this question.
What interleaving does is provide your vertex data with better cache-coherence; i.e. all of the attributes to specify a vertex will fit in a GPU cache line and can be read by the hardware in a single operation, rather than having to jump around multiple disjoint memory locations. Irrespective of whether or not you use VAOs, if you don't interleave you're going to have to do that jumping around.
Where a VAO may help is by batching state changes required to specify your vertex layout into a single operation, but again this would be irrespective of whether or not you interleave. They really are completely separate concepts.