Managing and speeding up queries on PostgreSQL table with over 3 trillion rows
Your existing index on DATE is obviously useless for the query. The first obvious step for your query:

SELECT * FROM tbl WHERE column_a = 'value1' AND column_b = 'value2';


is an index for column_a or column_b (which ever is more selective) or possibly a multicolumn index on (column_a, column_b), like:

CREATE INDEX tbl_a_b_idx ON tbl(column_a, column_b);


Details:


Is a composite index also good for queries on the first field?


Next, I would consider partial indexes if you can safely exclude large parts of the table from the queries. Or partition your table in something like 100 partitions. And use constraint exclusion.

"Splitting it by year", like you contemplated, would be just as useless (harmful, even) as your index on DATE for the given query. Partitions need to be based on columns in the predicates of the query (column_a and column_b) to be helpful. Predicates on just one column would be much easier in this respect. If you have important queries filtering on various columns, partitioning is probably not the way to go. (Partial indexes still might.)

If partitioning is no good, a less invasive measure would be to CLUSTER data based on the new index (you can't use a partial index for this). Or simply create a new table from the sorted output of a query. This is particularly interesting since your table is mostly read-only. It should pay to do this at least once, but that one time will be very expensive: the whole table has to be re-written one or the other way. You need enough free space, as much RAM as you can get and an exclusive lock on the table. Or use pg_repack, to avoid the exclusive lock:


Configuring PostgreSQL for read performance
Best way to populate a new column in a large table?


Be sure to run the latest version of Postgres. The upcoming Postgres 9.5 might be particularly interesting for you, since it introduces BRIN indexes (block range indexes), which can reduce the index size dramatically for very big tables. Might be exactly what you are looking for.