Gracias a la ayuda de Carlos Quitenro ya tengo el formulario dínamico funcionando.
La única modificación que necesitaría para que fuera perfecto sería añadir un valor máximo a la variable "contador" para evitar que el usuario intente enviar mas contactos de los que la tabla de mysql donde se envían admite.
Este es el código que tengo ahora:
<html>
<head>
<title>Webslesson Demo - Dynamically Add or Remove input fields in PHP with JQuery</title>
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css" />
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/js/bootstrap.min.js"></script>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.2.0/jquery.min.js"></script>
<link href='jquery-ui.min.css' type='text/css' rel='stylesheet' >
<script src="jquery-3.2.1.min.js" type="text/javascript"></script>
<script src="jquery-ui.min.js" type="text/javascript"></script>
<meta charset="utf-8">
</head>
<body>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div class="container">
<br />
<br />
<h2 align="center"><a href="http://www.webslesson.info/2016/02/dynamically-add-remove-input-fields-in-php-with-jquery-ajax.html" title="Dynamically Add or Remove input fields in PHP with JQuery">Dynamically Add or Remove input fields in PHP with JQuery</a></h2><br />
<form action="data.php" method="POST">
<table class="table table-bordered" id="dynamic_fieldcli">
<td colspan="3" align="center" style="color:#FFFFFF" bgcolor="#00CCFF"><b>DATOS DEL CLIENTE</b></td>
<tr>
<td>
<div class="col-xs-4">
<label for="ex1">Cliente</label>
<input class="form-control" name="nombrecli_1" placeholder="Enter your Name" id='nombrecli_1' type="text">
</div>
<div class="col-xs-5">
<label for="ex1">Referencia Facturación </label>
<input class="form-control" name="referencia_cliente" placeholder="Introduce la referencía de facturación" id='referencia_cliente' type="text">
</div>
<div class="col-xs-3">
<label for="ex1">Orden de carga</label>
<input class="form-control" name="ordendecarga" placeholder="Sube la orden de carga" id='ordendecarga' type="file">
</div>
</td>
</tr>
</table>
<div class="lista2">
<div class="group" id="1">
<table class="table table-bordered" id="dynamic_fieldcli">
<td>
<div class="col-xs-3">
<label for="ex1">Contacto</label>
<input class="form-control" name="nombrecon_1" id="nombrecon_1" type="text">
</div>
<div class="col-xs-3">
<label for="ex2">Teléfono</label>
<input class="form-control" name="telefonocon_1" id="telefonocon_1" type="text">
</div>
<div class="col-xs-5">
<label for="ex3">Mail</label>
<input class="form-control" name="mailcon_1" id="mailcon_1" type="text">
</div>
<a href="#" data-id="1" onClick="agrega()" class="btn btn-success">+</a>
</td>
</table>
</div>
</div>
<button class="btn btn-success" type="submit">Submit</button>
</form>
</div>
</body>
</html>
<script type="text/javascript">
var contador = 1;
function agrega(){
contador = parseInt(contador) + 1;
var item = `<div class="group" id="`+contador+`">
<table class="table table-bordered" id="dynamic_fieldcli">
<td>
<div class="col-xs-3">
<label for="ex1">Contacto</label>
<input class="form-control" name="nombrecon_`+contador+`" id="nombrecon_`+contador+`" type="text">
</div>
<div class="col-xs-3">
<label for="ex2">Teléfono</label>
<input class="form-control" name="telefonocon_`+contador+`" id="telefonocon_`+contador+`" type="text">
</div>
<div class="col-xs-5">
<label for="ex3">Mail</label>
<input class="form-control" name="mailcon_`+contador+`" id="mailcon_`+contador+`" type="text">
</div>
<button onClick="elimina(`+contador+`)" data-id="`+contador+`" class="del">Eliminar</button>
</td>
</table>
</div>`;
$(".lista2").append(item);
}
function elimina(x){
$("div[id="+x+"]").remove();
contador = 0;
$(".lista2 .group").each(function(){
contador = parseInt(contador) + 1;
$(this).attr('id',contador)
$(this).find('input.form-control').attr('id','nombrecon_'+contador+'')
$(this).find('input.form-control').attr('name','nombrecon_'+contador+'')
$(this).find('input.form-control').attr('id','telefonocon_'+contador+'')
$(this).find('input.form-control').attr('id','mailcon_'+contador+'')
$(this).find('input.form-control').attr('name','telefonocon_'+contador+'')
$(this).find('input.form-control').attr('name','mailcon_'+contador+'')
$(this).find('button.del').attr('data-id',contador)
$(this).find('button.del').attr('onClick','elimina('+contador+')')
})
}
</script>