If you do not have privilege for "Show Status" then, The best option is to, create two triggers and a new table which keeps the row count of your billion records table.
Example:
TableA >> Billion Records
TableB >> 1 Column and 1 Row
Whenever there is insert query on TableA(InsertTrigger), Increment the row value by 1 TableB
Whenever there is delete query on TableA(DeleteTrigger), Decrement the row value by 1 in TableB