We give a complete characterization of the secrecy capacity of arbitrarily varying wiretap channels (AVWCs) with correlated random coding under a strong secrecy criterion where the eavesdropper may also know the correlated randomness. We obtain that the correlated random coding secrecy capacity is continuous as a function of the AVWC. We show that the deterministic coding secrecy capacity of the AVWC either equals 0 or the correlated random coding secrecy capacity. For the case that only a weak secrecy criterion is applied, a complete characterization of the corresponding secrecy capacity for deterministic codes is possible. In the proof of the secrecy capacity formula for correlated random codes, we apply an auxiliary channel which is compound from the sender to the intended receiver and varies arbitrarily from the sender to the eavesdropper. We discuss the relation between the usual mutual information secrecy criterion and a criterion formulated in terms of total variation distance, and investigate the robustness of the AVWC model.