A locução ter a ver com significa "ter relação com" (ex.: essa questão tem a ver com outro assunto) e a locução verbal ter a haver significa "obter, receber" (ex.: Eles têm a haver uma fortuna com a herança), apesar de não ser muito usual.

Assim, quer a frase Ele não tinha nada a ver com o crime (parafraseável por Ele não tinha relação com o crime) quer a frase Ele não tinha nada a haver com o crime (parafraseável por Ele não tinha nada a receber com o crime) estão correctas, sendo a primeira hipótese a mais provável como resposta para a dúvida que nos colocou, dado que a locução ter a ver com suscita frequentemente dúvidas aos falantes do português devido à semelhança fonética com ter a haver.

O FLiP (http://www.flip.pt) inclui um corrector sintáctico que detecta, entre muitos outros, erros na construção de locuções, sendo de grande utilidade na resolução de dúvidas como a que nos expôs.

Ver também: ter a ver com / ter que ver com; não ter nada a ver / não ter nada a haver; ter a ver com / ter haver com

Notas

1. As respostas são datadas e escritas segundo a ortografia da norma europeia anterior ao Acordo Ortográfico de 1990.
2. A base do dicionário foi alterada a 1 de Abril de 2009, pelo que as referências em dúvidas anteriores a esta data podem não corresponder ao conteúdo actual.
3. As respostas sobre questões ortográficas são maioritariamente baseadas na norma ortográfica portuguesa de 1945, contendo as respostas mais recentes indicações sobre a ortografia antes e depois do Acordo Ortográfico de 1990.
4. A bibliografia utilizada está disponível aqui.