It think that this is easiest to do with temporary commits. When you have staged and unstaged commits, you have the possibility of conflicts when trying to reorder the changes.
Make a commit with the staged changes, create a branch for later use:
git commit -m "Saved staged"
git branch save-staged
Make a commit with the unstaged changes (if the unstaged changes include new files you may need to explicitly git add them first):
git commit -a -m "Unstaged changes"
Rebase the unstaged changes onto the original HEAD (may involve conflict resolution):
git rebase --onto HEAD^^ HEAD^
Rebase the staged changes onto the unstaged changes (may involve conflict resolution):
git reset --hard save-staged
git rebase --onto HEAD@{1} HEAD^
Finally, reset the index to the (originally) unstaged changes:
git reset HEAD^
And move the branch pointer back to the original HEAD:
git reset --soft HEAD^
Removed temporary branch:
git branch -D save-staged