You can either pull down those changes to your local branches, and solve any problems before pushing (which you might have to resolve on your other machine on the next pull otherwise), or you can push to specific branches with the :-notation.
git push origin [local-branch]:[remote-branch]
Which also is the way to delete remote branches (i.e. git push origin :branch
would push an empty branch to the specified remote-branch, thus deleting it).
This shouldn't touch any other branches at all. (if however there are external changes in the branch, take care to merge these in before force-pushing at all, by for instance branching onto a new branch for this).
Actually, now that I think about it, the better solution is to push the rebased branch to a new branch on the remote, instead of force-pushing to the current branch. (And then possibly deleting the old un-rebased branch if it's no longer needed), which would make for the least breakage.