Why is a new user allowed to create a table?
When you create a new database, any role is allowed to create objects in the public schema. To remove this possibility, you may issue immediately after the database creation:

REVOKE ALL ON schema public FROM public;


Edit: after the above command, only a superuser may create new objects inside the public schema, which is not practical. Assuming a non-superuser foo_user should be granted this privilege, this should be done with:

GRANT ALL ON schema public TO foo_user;


To know what ALL means for a schema, we must refer to GRANT in the doc, (in PG 9.2 there are no less than 14 forms of GRANT statements that apply to different things...). It appears that for a schema it means CREATE and USAGE.

On the other hand, GRANT ALL PRIVILEGES ON DATABASE... will grant CONNECT and CREATE and TEMP, but CREATE in this context relates to schemas, not permanent tables.

Regarding this error: ERROR: no schema has been selected to create in, it happens when trying to create an object without schema qualification (as in create table foo(...)) while lacking the permission to create it in any schema of the search_path.