This is how I eventually solved it.
Incorporating @carlos's input I used Ryan Bates's helper for dynamically adding new nested_attributes fields but altered it to work in my list of cities
<%= form_for(individual) do |f| %>
<% for city in cities.each do %>
<% if individual.visits.include?(city) %>
<% visit = f.object.visits.find_by_city_id(city.id) %>
<%= f.fields_for(:visits, visit, child_index: visit.id ) do |existing_visit| %>
<tr>
<td>
<%= check_box_tag "individual[visits_attributes][#{visit.id}][city_id]", city.id, individual.visits.include?(city) %>
<%= existing_visit.hidden_field :_destroy %>
</td>
<td>
<label>How good was your visit here?</label>
<%= existing_visit.select :sentiment, options_for_select([ ...... ])) %>
</td>
<td>
<label>What was the weather like?</label>
<%= existing_visit.select :weather, options_for_select([ ...... ])) %>
</td>
<td>
<label>Where did you stay?</label>
<%= existing_visit.select :accomodation, options_for_select([ ...... ])) %>
</td>
</tr>
<% end %>
<% else %>
<% visit = f.object.visits.build %>
<% random_index = city.id.to_s+"_"+Time.now.to_i.to_s %>
<%= f.fields_for(:visits, visit, child_index: random_index) do |new_visit| %>
<tr>
<td>
<%= check_box_tag "individual[visits_attributes][#{random_index}][city_id]", city.id, nil %>
</td>
<td>
<label>How good was your visit here?</label>
<%= new_visit.select :sentiment, options_for_select([ ...... ])) %>
</td>
<td>
<label>What was the weather like?</label>
<%= new_visit.select :weather, options_for_select([ ...... ])) %>
</td>
<td>
<label>Where did you stay?</label>
<%= new_visit.select :accomodation, options_for_select([ ...... ])) %>
</td>
</tr>
<% end %>
<% end %>
<%= f.submit "Update", :class => "btn" %>
<% end %>
<% end %>
The key was in using an if statement to check whether the record was a new record or existing and then correctly setting the child_index: on the fields_for helper.
I also had to use the check_box_tag rather than .check_box helper so that it didn't produce the hidden check box field.
I use Javascript to trigger the hidden field to delete a record when the user unchecks the box next to the city that the visit took place.
Get in touch if you need more details.