**Revised answer** (see previous version to make sense of comments):

The Petersen graph is a small wonderful and rather exceptional creature. It is not a paradigm.

Does this graph fit your construction with $G = C_7$, $H = K_2$ ?

![alt text][1]

It is not vertex transitive since each red node is in three $5$-cycles but each green node is only in two.

There are many vertex transitive graphs with a prime number of vertices, none of them is a product. So there are graphs which do not arise in this manner. 

Your construction takes two graphs $G_i$ with $v_i$ vertices each of degree $d_i$ and some permutations and creates a new one with $v_1v_2$ vertices each of degree $d_1+d_2.$ This can work out to be a rather low degree (or high if a complement is taken.) Consider the Johnson graph $J(6,2)$ whose $\binom{6}{2}=15$ nodes are the pairs from an $6$ set with two adjacent when they share an element. It has degree $2(6-2)=8.$ If it is to be a product then we need $v_1=3$ and $v_2=5$ which allows for degree at most $2+4=6.$ This also does not allow the product to be the complement a regular graph of degree $7.$ A similar obstacle would arise for  many vertex transitive graphs just based on the number of vertices and the degree. Certainly for $J(n,2)$ when $n \ge 6$ makes $\binom{n}2$ odd and probably even when $\binom{n}2$ it is even.

  [1]: https://dl.dropbox.com/u/24793671/monotvt.png