Proving a language comprised of 2 languages is regular(with suffix and prefix)
Your language is the concatenation $\Sigma^* L \Sigma^*$, where $L$ is the so-called perfect shuffle of $L_1$ and $L_2$. There are at least two proofs that the perfect shuffle of two regular languages is regular on this site: using automata and using closure operations.

If you are hell-bent on constructing an automaton for $\Sigma^* L \Sigma^*$, start with one for $L$, then follow the automata proof of closure under concatenation (which constructs an NFA).