How to register data in a database by clicking on a HREF?

The form would be with ajax.

$mensaje = "<a onclick='guardar(".$user.")'>No Friends</a>";

JS

<script>
    function guardar(id) {
        $.ajax({
            type: "POST",
            url: "tu url",
            data: {
                iduser:id,
            },
            error: function (jqXHR, textStatus, errorThrown) {
                alert(errorThrown);
            },
            success: function (data, textStatus, jqXHR) {
                alert("se añadio el amigo");
            }
        });
    }
</script>

PHP TO SAVE

<?php
    $idusuario = $_POST['iduser'];
    //haces tu inserción

I would put this as a comment, since it is not part of the answer, but note in the WHERE of your query

WHERE (User_one ='$my_id' AND User_two = '$user') OR (User_two = '$user' AND User_one = '$my_id') 

Both conditions are the same, I think you wanted to put this

WHERE (User_one ='$my_id' AND User_two = '$user') OR (User_one = '$user' AND User_two = '$my_id')

As for your problem, I think of this as a solution Change the else to something like this:

$mensaje = "<a href='#' id='id".$user."' class='enlace'>No Friends</a>";

The question is to create the tag id, and to register the value of the friend you want to insert, if the id is 35, the label would be 'id="id35" and the class field, will serve to make the call to the Ajax event.

Then by Ajax, you could do the insert

<script type="text/javascript">
     $( document ).ready(function() {
          $(".enlace").click(function(){
              var id= $(this).attr('id');
              $.ajax({
                    type: 'POST',
                    url:" ", //Direccion de tu fichero php, que va a realizar la inserción
                    data: {id:id.replace(/\w/g,'')},
                    beforeSend: function(){
                        //Puedes poner una animación mientras se hace la inserción
                    },

                    success: function(data) {
                        var error=data.datos[0].error;  //Valor que te retornaría tu php, indicando si se ha guardado el amigo

                        if (error==1){ //Por ejemplo se ha insertado
                            $("#"+id).html('Already Friends');
                            $("#"+id).removeAttr('class');
                        } else{
                            alert("Error al realizar la insercion")
                        }
                },

                    error: function (response) {
                        alert("Error en el proceso");
                    }
                });
            }

        });
    });
</script>

Assuming you have a link like this:

<a href="/amigos/agregar?uuid=ab3853f4950p9" 
    onclick="agregarAmigo(event)">Agregar amigo</a>

Just make a simple AJAX request:

function agregarAmigo(ev) {
  ev.preventDefault();
  const URI = ev.target.href;
  let xhr = new XMLHttpRequest();
  xhr.open('GET', URI);
  xhr.onload = () => {
    if(xhr.status === 200 && xhr.readyState === 4) {
      // mostrar banner o algo que informe que ha sido agregado
    }
    if(xhr.status === 500) {
      // mostrar error
    }
  };
  xhr.send();
};

And on the backend:

$targetUUID = $_GET['uuid'];
$userUUID = $_SESSION['uuid'];

$query = /* tu query */;
$result = mysqli_query($conn, $query);

if($result == FALSE) {
    http_response_code(500);
    echo 'Ha ocurrido un error';
} else {
    http_response_code(200);
    echo 'Amigo agregado';
}