ERROR: no schema has been selected to create in

I am working on an amazon RDS postgresql database where I know there had been some issue with the public schema (maybe it was dropped). But apparently the schema exists, and anyway the problem is not solved. Here is a sample session with a newly created empty database:

mydb=> CREATE TABLE distributors (
mydb(>     did     integer,
mydb(>     name    varchar(40) UNIQUE
mydb(> );
ERROR:  no schema has been selected to create in
mydb=> show search_path;
  search_path   
----------------
 "$user",public
(1 row)

mydb=> create schema public;
ERROR:  schema "public" already exists

Any hint? What should I look for?

Solved.
Thanks to the answer of Daniel Vérité I've solved with the following:

grant usage on schema public to public;
grant create on schema public to public;

Are these the default permissions on the public schema?

I have a single user who can access the database, so I think this anyway cannot raise security risks...

I think I should make the same modification on template1. Is it correct? How can I check if the permissions in template1 are correct (say, default values)?

This happens when not having USAGE privilege on any of the schemas of search_path. By default the pseudo-role public (all users) has this privilege on the publicschema, so this error happens only after revoking it explicitly with:

revoke usage on schema public from public;

This is required when it's not desirable that people peek into other people schemas, even without selecting data from tables (which is granted through different privileges).

If this REVOKE hasn't been done in that database, it may have happened in the template database by which new databases are modelled (see CREATE DATABASE).

When a user has USAGE privilege, but lacks CREATE privilege on the schema, it's a different error when trying to create an object: permission denied for schema public.

To check the privileges inside psql, use \dn+ public.

By default (shown with extended display \x for readability):

# \dn+ public
List of schemas
-[ RECORD 1 ]-----+-----------------------
Name | public
Owner | postgres
Access privileges | postgres=UC/postgres
| =UC/postgres
Description | standard public schema

lack of a rolename before = means it's for all roles (=public)

Without public USAGE privilege

Name | public
Owner | postgres
Access privileges | postgres=UC/postgres
| =C/postgres
Description | standard public schema

Without public USAGE or CREATE privileges

Name | public
Owner | postgres
Access privileges | postgres=UC/postgres
Description | standard public schema

StackExchange Database Administrators Q#106057, answer score: 49