no additional field in the database - through algorithm the promotional code can be decoded back to userid
While this would usually be solved through an additional table with cross references, ideally 1:n, so that one user id can have multiple valid promotional codes, this seems to be explicitly out of scope. This also precludes self-chosen promocodes, unfortunately.
hard to guess the userid
Ideally, it shouldn't be possible to guess the user id (and be sure you guessed right) at all.
easy to share verbally
This might be the biggest problem with not using an additional table.
I propose the following solution:
Encrypt your user ids.
There are different encryption schemes that may yield smaller results that can be used. But if, as suggested by your restriction on changes to the database, implementation cost is a driving factor, raw rsa might be worth a look as it keeps the ciphertext relatively small and encryption libraries are readily available.
The resulting bits could be translated into natural language words, for example by using a wordlist for diceware.
Using this approach, the ciphertext would be easy to communicate (as it's a string of words) and easy to decipher (reverse translation, decrypt resulting bits).
There is however a catch: those codes might get longer than expected (depending on the chosen encryption scheme) and might pose a time penalty when it comes to typing them in.
While this yields longer (in terms of string size) codes, they are way easier to transmit verbally especially for native speakers than the result of base32, base64 or any of the usual approaches for transport encoding.
Thus, even though a 1:n table would be ideal, using a fitting encryption scheme and ending up with maybe a 3 word code might be the next best thing - and definitely easier to share verbally than the usual suspects for encoding data.