If you have statistics collected on the tables, you can query the catalog and find tables without any rows. But you are right that those statistics could be outdated. However, in such a situation you probably have a different problem anyway: if the stats are not up to date, you have a good chance that the optimizer is picking sub-optimal access paths. So it is usually a good idea to make sure the statistics are more or less up to date.
What you could do is this: for all important tables you keep the stats up to date and rely on the stats. For all other tables, you have to query the table itself.