Create new Mecanim parameter from code?

Ok, I solved it. The key is to cast the Runtime Animation Controller the Animator class provides to an AnimationController and then it's easy to add new parameters using the .AddParameter method.

(only possible in the Editor, because it uses UnityEditor.Animations)

 using UnityEngine;
 using UnityEditor.Animations;
 
 public class ParameterTest : MonoBehaviour
 {
     protected void AddParameter ()
     {
         // We first need to get the animator attached to this object
         // and then cast it's runtimeAnimationController
         // to an AnimationController
         Animator animator = GetComponent<Animator> ();
         AnimatorController animatorController = (AnimatorController) animator.runtimeAnimatorController;
 
         // Method 1, keeps reference to the parameter
 
         AnimatorControllerParameter parameter = new AnimatorControllerParameter ();
         parameter.type = AnimatorControllerParameterType.Bool;
         parameter.name = "NewParameter1";
 
         animatorController.AddParameter (parameter);
 
         // Method 2, shorter, but without a reference
 
         animatorController.AddParameter ("NewParameter2", AnimatorControllerParameterType.Float);
     }
 }