Please include pilot and the original series, if that is pertinent.
In the Star Trek Interview Book, Allen Asherman says that Deforest Kelley claims that Gene Rodenberry offered him the role before production of The Cage began. Another source I've seen, however, says that when Rodenberry saw Nimoy's features, no other actors were ever considered over Nimoy. There was however, a backup plan if Nimoy turned the role down: Martin Landau*
*I believe the source for that was Star Trek Creator, but I'm not entirely sure.
@FinalDraft is right about Martin Landau. He (Martin Landau) is interviewed about this in the PBS Pioneers of Television: Science Fiction episode. Martin Landau doesn't sound like he would have enjoyed the part, had he even been offered it.