Material whose dielectric constant * [dielectric strength]^2 > 20,000,000,000
If by dielectric strength you mean V/m then"it's easy".
If you mean MV/m then probably only diamond has a chance of qualifying, and probably doesn't. 

Here is Wikipedia DS page.
The table of strengths indicates that for diamond to be suitable the dieletric constant would need to be.   

2,000,000,000/2000^2 = 500 

Reported values are in the 5 - 10 range.





Another approach is to look at material with high DC as a starting point.
Barium titanate is one of the highest wity reported values in the 4000-6000 range.   As this is usually sintered from a powdered form air voids and similar affect results.
Dielectric strength is not marvellous [tm] but eg this paper Improved dielectric strength of barium titanate-polyvinylidene fluoride nanocomposite using barium titanate reports


Barium titanate-polyvinydene fluoride nanocomposites with improved dielectric strength were prepared, in which on the surface of the barium titanate nanoparticle was coated. The results showed that the dielectric breakdown strength of the nanocomposites increase significantly up to 250 kV/mm and then decrease. 


250 kV/mm = 250 MV/m. At say (one can hope) DC of 6000 that still gives a figure of merit of 6000 x 250^2 = 375 million, or only about 20% of your target value. 

As the greatly improved DS is achieved by coating and thus disprsing the barium titanate particles within the polyvindene I'd expect that the DC would be much lowered. 



From here



Barium Titanate:

http://www.intechopen.com/books/ferroelectrics-material-aspects/barium-Barium Titanate-Based Materials – a Window of Application Opportunities

The Overview of The Electrical Properties of Barium Titanate

Dielectric and Piezoelectric Properties of Barium Titanate

https://en.wikipedia.org/wiki/Barium_titanate

Possible interest

Giant polarization in high polymers

Diamond

http://www.nature.com/nature/journal/v161/n4097/abs/161729a0.html

http://pubs.rsc.org/en/content/articlelanding/1940/tf/tf9403500575#!divAbstract

Reference:

https://en.wikipedia.org/wiki/Dielectric_strength

Silver Mica Capacitor - an overview or tutorial about the basics of the silver mica capacitor, its construction, properties and the uses of silver mica capacitors particularly in RF circuits.

Mica