I use previous_post_link() and next_post_link() (Codex previous_post_link()/next_post_link()) outside of the Loop, with no problems.
Note that the Codex entries indicate that these functions must be used within the Loop, but IMX that isn’t true. The functions call the $post global, and pass it to get_previous_post() and get_next_post(), respectively.
By the way, posts_nav_link() is the incorrect function to use in the single-post context, anyway. It is intended for navigation of archive index pages, not of single posts.