Do we require a token module for token_replace() to work?
You don't need the Token module to use the functions you mentioned in your question. They are defined in Drupal core.

References:


token_replace()
hook_token_info()
hook_tokens