How to relate nodes by field, not title?
You are mistaken. Node reference uses the node id - the primary key for nodes to create the reference. The form element where you need to enter the node you want to reference, uses autocomplete to make it easier to find the node you want to reference, but the value stored is the node id. So there is actually no problem in using node reference and changing the title.

Code from the node reference module to illustrate this, can be found where the schema is defined for the field type it uses to create these reference:

/**
 * Implements hook_field_schema().
 */
function node_reference_field_schema($field) {
  $columns = array(
    'nid' =&gt; array(
      'type'     =&gt; 'int',
      'unsigned' =&gt; TRUE,
      'not null' =&gt; FALSE,
    ),
  );
  return array(
    'columns' =&gt; $columns,
    'indexes' =&gt; array('nid' =&gt; array('nid')),
    'foreign keys' =&gt; array(
      'nid' =&gt; array(
        'table' =&gt; 'node',
        'columns' =&gt; array('nid' =&gt; 'nid'),
      ),
    ),
  );
}