How to add links to sidebar without using a block?
Can be done using the  _phptemplate_variables function in template.php in your theme directory.

function _phptemplate_variables($hook, $vars) {
  if ($hook == 'page') {
    foreach (array('left','right') as $region) {
      $vars[$region] = drupal_get_content($region);
      return $vars; 
    }
  }
}


And just call this function below where you want to display the link.

$output = l('some link text','node/1234');
drupal_set_content('left', $output);