MySQL 4.0 doesn't have information_schema and 'show table status from db' only gives approximate row count for innodb tables.
So whats the quickest way to get the count of innodb tables, of course other than count(*), which could be slower with big tables.
Updated
When using InnoDB the only accurate count of rows in your entire table is COUNT(*). Since your upgrade from 4.0 to 5.0 will only occur once, you'll just have to deal with the speed.
Well, using * is definitely not optimal but how about just 1 column. I usually use the id column to count # of rows.
This applies to all versions of MySQL. As other commenters have pointed out - there is no fast SELECT COUNT(*) in InnoDB. Part of the reason for this is that InnoDB is multi-versional, and it will depend on the context of your transaction how many rows there are supposed to be in a table.
There are some workarounds:
1) If you never delete, SELECT MAX(id) should return the right number of rows.
2) Instead of deleting rows, you can archive them to a 'deleted rows table' (a lot of people seem to want to keep everything these days). Assuming that the delete is a much smaller subset of still current, you may be able to subtract count(*) from deleted_rows from SELECT max(id) from not_deleted.
3) Use triggers. This sucks for performance.
There's quite a technical discussion on this problem here: http://mysqlha.blogspot.com/2009/08/fast-count-for-innodb.html