There will be a *lot* of manual cleanup required... good luck!
I would suggest that regularizing the data first would probably be
the best approach. For instance, replace " North Dakota" with ",
ND", and so forth (as well as all variations). If that leads to a
double comma, you easily run an update to replace ",," with ",".
This is fussy work, but I think it's better to do it in a single
field than it is to have to move stuff around manually between
different fields.
Another thing to consider is that you might find it useful to write
code that can use the Split() function to store the value in an
array, using, say " " as a delimiter. Then you could walk from the
end of the array examining what's in each item and acting
accordingly, then placing that in the appropriate field. You could
do something like taking the last item in the array, stripping out
"-" and then testing IsNumeric(). If that's true, then it's very
likely a zip code (heaven help you if there's Canadian records --
then you'd have to check if it alternated letters and digits).
Once you've processed out the zip code, then you can see if the next
item in the array matches a table of state names/abbreviations. If
so, you can put that in the state field.
If it's not, you'd check to see if combining that value and the
previous value with a " " in between matches your lookup table.
Once you've got a match, you'd then move to the next part, and if
you're lucky, you can process it against a zip code table and use
your already derived zip code to intelligently figure out what the
possibilities for the city name are.
Once you've parsed all of that, the remainder should, in theory, be
the address.
Coding this could be very difficult, and depends on having good
lookup tables. But if you need to do this for a large amount of
data, that's likely how I'd approach it.
Another alternative is to go back to the original source and ask if
you can get the data in a proper format!