I agree with Tybond that it's very possible, since I did it, but I differ on some of the details.
First, you don't NEED a sand bed if you don't want one. The reason live rock works to cycle your tank is that it has both the dead stuff on it and the bacteria to eat it up. Whatever you use for substrate, the bacteria from the live rock will spread to it without the necessity of buying live sand. Of course, I prefer sand, but it's not necessary.
Second, I don't use hermit crabs. Ron Shimek has said, and it makes sense, that hermit crabs will decimate the 'critter' population of your reef. So when I got my algae bloom, I bought some snails, and they made short work of it.
Third, some small stuff on your rock will probably die, but IMHO, it's still a better way to cycle.
Finally, if I were you, I'd use UNCURED rock to cycle with. You'll have more 'food' for the bacteria, and you typically have more life in uncured rock....