Let's set up a series of types that are defined as "v1" storage. We can do a migration to v2 storage all in one fell swoop. The runtime then doesn't need to worry about upgrades to one storage type at a time and the node-side code can use a primitives-version runtime API to know exactly which types to provide at any time.

The runtime has a hard time with types that refer to the block hash or number type concretely, as it has to use system::BlockNumber and system::Hash types and can't specialize them.

So we should set up types as generic, typically as

struct SomePrimitive<H = Hash, N = BlockNumber> {
    relay_parent: H,
    relay_parent_number: N,
}

All primitive types should be rewritten this way.
And all code using primitive types should be retargeted towards v1 primitives.
Runtime code should be using explicitly instantiated versions with <T as system::Trait>::BlockNumber and <T as system::Trait>::Hash (usually T::BlockNumber and T::Hash for short), while node-side code will use the default instantiations.

This is considered substantial only because of the amount of code that needs to be changed. However the default instantiations should cut down on that a lot.

When we move onto v2, most types will be exactly the same. Instead of re-declaring them I figure we can just define stuff like this

mod v2 {
    pub use v1::{TypeA, TypeB, TypeC};

    struct TypeD<H = Hash, N = BlockNumber> { ... }
}

And we can also establish some global primitives like BlockNumber and Hash, which should never change, but best to leave those as minimal as possible.