The 24 nations with the largest Catholic populations all are currently represented by cardinals.
Of all nations without cardinals, Bolivia has the largest Catholic population. About 8 million of its 10.5 million people (75%) are Catholic. It has been represented by two cardinals in the past. Guatemala is second in terms of Catholic population, but it has also been represented in the past. Paraguay, with about 6 million Catholics out of 6.8 million people (90%), is third and has never been represented by any cardinals.
It may also interest you to note the nation with the highest proportion of Catholics and no cardinal. Aside from the Vatican, that honor belongs to East Timor, formerly a part of Indonesia (which has had cardinals in the past), with about 97% of its one million people being Catholic.
I primarily used the tables in Wikipedia's list of living cardinals and Catholicism by country articles, but both tables required a little bit of massaging. The spreadsheet I created is available for download here.