Are there any examples of proteins with no or minimal sequence identity, but highly similar structure?
This paper published last year, address the answer for your question, about computational methods, they mention 3 principal algorithms for structural alignment
of proteins:


Structural alignment directly at the level of C atoms. 
The second class of algorithms first uses the SSEs (Secondary Structure Elements) to carry out an approximate alignment, and then uses the C atoms.
The final class of algorithms uses geometric hashing.


And finally you could find useful this paper for an example of this kind of analysis with structural analyses of metabolic families.

References:


 Venkateswaran JG, Song B, Kahveci T, Jermaine C. TRIAL: a tool for finding distant structural similarities. IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM 8: 819–31.
 Marsden RL, Ranea JAG, Sillero A, Redfern O, Yeats C, Maibaum M, Lee D, Addou S, Reeves GA, Dallman TJ, et al.. 2006. Exploiting protein structure data to explore the evolution of protein function and biological complexity. Philosophical transactions of the Royal Society of London Series B, Biological sciences 361: 425–40.