How do I change date format in the submitted line using only template.php without node.tpl.php?
You can use template_preprocess_node to alter submitted variable. Here is the sample code.

function awesome_preprocess_node(&amp;$variables) {
  $node = $variables['node'];
  $date = format_date($node-&gt;created, 'custom', 'm-d-Y - H:i');
  $variables['submitted'] = t('Submitted by !username on !datetime', array('!username' =&gt; $variables['name'], '!datetime' =&gt; $date));
}


The most important line there is $date = format_date($node-&gt;created, 'custom', 'm-d-Y - H:i');. Change the format (m-d-Y - H:i) to any format you want. 

See this page about PHP date format.