Index-based approach is honest work, not a compromise. I've shipped plenty of data structures this way and it's straightforward to reason about.
The Rc<RefCell> crowd will tell you it's idiomatic, but you're trading compile-time guarantees for runtime panics. Arenas are great if you control the entire lifetime, but adds complexity most projects don't need.
Your Vec index solution scales fine. Just be disciplined about validity (don't delete nodes without cleanup logic). Way better than fighting the borrow checker for ego points.