Can I expect the
getnewaddress command to work before my
bitcoind has finished synchronizing?
getnewaddress works independent of the downloading and indexing of your blockchain database.
The command will generate a new private key in your wallet.dat file. This file is independent of the state of your blockchain files.
Your new address is derived from the freshly generated private key.
Your client will need to be synced to see incoming transactions (deposits) on your address reflected in your balance.