How to display link to the next/previous most recent node from current node (if it does not belong to a book)? I would like to display the next and the previous most recent node from the current node (if it does not belong to a node).

It is somewhat similar to the pager available to the book page, except here the current node as well as the links to the next/previous nodes are not in a hierarchy and do not belong to a book.

Assuming I have 4 nodes - node1,node2,node3,node4 (all belonging to a set of node types I want to use) and each published consecutively one after the other. Then if the user is on node3, he/she should see the links for node2 and node4. If currently on node2 then node1 and node3 links should show up. If they navigate to node1, then a link for node2 should be displayed and so on and so forth.

Also, the  next and previous nodes can only belong to a pre defined set of node types.

I am using D7 and wouldn't mind using either a custom function or a views block to implement this. Any ideas on how to go about it?
You can do it with db_query in your node--content_type.tpl.php. Get all nids for content type in array. Match the current nid position in array. Like if Position is array[3] the Previous nid link should be array[2] and next should be array[4].