Is there anyway of doing this by using rules or by some custom code? I did try using rules but I can't find a way of adding a new term and set the name as the node title because the [node:title] token is not avilable.
I know this is possible using the NAT module but the way this module changes the taxonomy terms hierarchy if you add a term reference field that uses the same taxonomy vocabulary which ruins the whole purpose of what I am trying to do.
At first glance, I would have two suggestions:
In Drupal 7, you can create fields per vocabulary, so perhaps it would be more interesting for you to create "one term with fields" instead of creating "one node with fields + one term" each time ?
Otherwise, whatever entity needs to reference your node thru its matching taxonomy term could directly reference the node instead (using a "Node Reference" field), that way you wouldn't need to maintain a separated vocabulary in parallel of your list of nodes.
But if you still want to create one term per node, then you should use the hooks that Haza mentioned.