When your ammonia and nitrite levels are at zero, and you are showing some nitrates, then your cycle is complete. I've never done a fishless cycle, so I think the nitrates are probably very high. If your tank is cycled, do a massive water change, like 75%, refill the tank, and add your fish. Make sure your nitrate level is below about 10 before adding your fish. 75% is a guess, and you may need to change out more than that to get the nitrates down to below 10.
Gunnie, youve never done a fishless cycle? What do you do to cycle tanks?
My first tank was cycled with fish. After that, I've either borrowed filter media, or used bio spira to cycle my tanks.