So in broad strokes, basically what you want to do is grab the user's uid and then open for editing the corresponding profile type node owned by that user.
So, if you have that user's uid in $uid, it would be something along these lines:
$nid = db_select('node', 'n')
->condition('n.type', 'YOUR_PROFILE_NODE_TYPE')
->condition('n.uid', $uid)
->fields('n', array('nid'))
->execute()->fetchField();
which, if I've not typo'ed anything will set $nid to the node id of the node of type YOUR_PROFILE_NODE_TYPE that is owned by $uid.
If there is only one, that's the node we are looking for.
So, now you just need to create a link to node/$nid/edit and you're all set. (Somewhat obviously, you want to present this link only to admins and the user who owns the profile.)
So, where do you put all of this?
Of course, you could preprocess this into a variable that's used in a page template, but you could also create a new menu item as well, eg user/#/edit-profile that grabs the user id out of the second argument and then does all of the above to grab the actual nid and then presents the node edit form, but now we are getting past the broad strokes :) (But hook_menu() is the place to look, with user.module a great starting point for example code for user/#/edit to modify)