How can compounds like XeO4 form tetrahedral structures despite having double bonds?
$\ce{XeO4}$ has a tetrahedral structure as you noted, but $d$-orbitals are not involved in explaining its geometry or hybridization. The central xenon atom in $\ce{XeO4}$ is best described as simply $\ce{sp^3}$ hybridized.  We have 8 xenon electrons so we need 4 orbitals to put them in.  The 4 equivalent orbitals are formed by mixing the $s$- and $p$-orbitals (just as we do with carbon) to form the equivalent $\ce{sp^3}$ orbitals pointing towards the vertices of a tetrahedron (which minimizes electron-electron repulsions between the 4 bonds). 

The molecule can be represented by several resonance structures and I've drawn two of them (A and B) below.  I've only drawn the lone pairs on one of the oxygen atoms for each resonance structure, but they are the same for all oxygens in each resonance structure.  So the resonance structures tell us that the xenon-oxygen bonds in $\ce{XeO4}$ are some mix of single and double bond character.  In resonance structure A, the xenon and oxygens are neutral; while in resonance structure B, the xenon has a charge of +4 and each oxygen has a charge of -1.



The $\ce{Xe-O}$ bonds in $\ce{XeO4}$ are very weak. In resonance structure A the pi overlap is very poor due to the different atomic sizes of xenon and oxygen. In resonance structure B we just have a simple single bond connecting the oxygen and xenon and it contains 2 electrons, both from xenon and shared by oxygen, oxygen does not contribute any electrons to this bond. The single bond resonance structure B probably contributes more to the description of this molecule than resonance structure A. The bonds are so weak that $\ce{XeO4}$ is unstable and explosively decomposes around -36 C. 

In summary we can say that 


the xenon in $\ce{XeO4}$ is $\ce{sp^3}$ hybridized
the $\ce{Xe-O}$ bond is a partial single-double bond with the single bond probably being a more accurate description, and 
the $\ce{Xe-O}$ bonds are extremely weak because of the poor pi overlap in resonance contributor A; and oxygen does not contribute any electrons to the xenon-oxygen bond in resonance contributor B.