As of writing, I could not find a way to get git-p4 to import additional paths from a Perforce clientspec directly.  However, I believe that I've devised a way to manually do it and have git-p4 honor it.
Disclaimer: I take no responsibility for any damage that the following steps might cause.  It probably would be a good idea to back up your .git tree first.
The idea
As you say, just adding a path to the Perforce clientspec and doing a git p4 rebase initially does not do anything.  However, I noticed that git p4 rebase will add files from that path after they are modified in Perforce and if the new path is within git-p4's depot-paths list. (depot-paths is the initial list of depot paths provided to git p4 clone.) Therefore you need:
- To get an initial copy of the new path into your Git repository.
- To trick git-p4into believing that it added that initial copy itself.
- To get git-p4to include the new path in itsdepot-pathslist.
Thus you can sync a copy of the files from Perforce, making sure that they're consistent with the files already imported from Perforce, and then you can explicitly add them to your Git repository.
git-p4 apparently does not store its depot-paths list nor the last imported Perforce change number anywhere other than in Git commit messages, so you can trick git-p4 by replicating its metadata in your own commit message.
Finally, you can move p4/master (and p4/HEAD, which is an alias to p4/master) to point to your new commit so that future git p4 rebase commands treat that commit as something imported from Perforce.
Step by step
- Check out the commit corresponding to - p4/master.  Make sure that you don't have any staged or unstaged changes.  Stash them if you do.
 
- Add the new path to the Perforce clientspec used by - git-p4.  In the steps below, I'll refer to this as- //depot/new/path/.
 
- Run - git logto look at the commit message from the Perforce change you last imported.  It will have a line that looks like:
 - [git-p4: depot-paths = "//depot/tree/": change = 12345]
 - Make a note of the Perforce change number. 
- In your Perforce client, sync your added path to that change number.  For example: - p4 sync //depot/new/path/...@12345
 
- Recursively copy those newly synced files from your Perforce client into the corresponding location in your Git repository. (Some care might be needed here if there are symlinks.) 
- Run - git addon that new path in your Git repository.
 
- Run - git commit.  You can mostly say whatever you want in your commit message (e.g. "Initial import of //depot/new/path/ from CLN 12345").  However, at the end of the message you must copy the- git-p4metadata line that you observed before:
 - [git-p4: depot-paths = "//depot/tree/": change = 12345]
 - If - //depot/new/path/is not a subdirectory of- //depot/tree, then you must amend- depot-pathsto add the new path:
 - [git-p4: depot-paths = "//depot/new/path/,//depot/tree/": change = 12345]
 - The - depot-pathslist must be sorted by ASCII value (i.e.,- //depot/foo-bar/should precede- //depot/foo/bar/).
 
- Run - git logagain.  Confirm that the- git-p4line in the commit message looks like ones from imported Perforce changes.  Make a note of the SHA1 hash of your commit.
 
- Navigate to the root of your Git repository.  Edit - .git/refs/remotes/p4/master.  Remove the old SHA1 hash listed and replace it with the SHA1 hash of your commit. (If- .git/refs/remotes/p4/masterdoes not exist, check- .git/packed-refsand update the appropriate line there.)
 
Now your Git repository includes a copy of the files from //depot/new/path/ from change 12345, and it should pick up any changes to those files from future Perforce changes.
Some other things of note
- Obviously the new path will exist in your Git repository only after your commit that imported those files, so - git bisectwon't be useful if it straddles that boundary and involves those files.
 
- Since modified files get automatically added if they're included in your Perforce clientspec (and are contained within - git-p4's- depot-paths), in some cases you potentially could avoid all of this work.  For example, if you know in advance that someone is going to be adding a new directory to the Perforce depot and that directory is already included by your- depot-pathsbut not by your clientspec, you can just preemptively add it to your Perforce clientspec.  You then should be able to get that new path automatically after it's actually added to Perforce.
 
- Alternatively you could add the new path to your Perforce clientspec and then submit a Perforce change that touches all of the files in that path.  I do not recommend doing that, however, as that could be disruptive to others (and imagine if everyone else did that).  I mention it only for completeness.