> What it doesn't protect you from is use-after-free bugs.

How about using hash maps/hash tables/dictionaries/however it's called in Rust? You could generate unique IDs for the elements rather than using vector indices.