So a couple of things - firstly, no, all routers connected to the Internet do not need the entire address space. If the device only has one connection to the Internet, they will have a default route eg: 0.0.0.0/0 pointed towards their upstream router and thats it. This represents any IP address that the router doesn't have a better route for.
Routers inside your ISP may contain the "entire" Internet routing table.
As to the second part of your question around the space required to hold the routing table - Internet routes aren't stored as individual host routes, but summary prefixes. The general rule for IPv4 Internet routes is that no ISP will advertise anything longer then a /24 (eg: a block of 255 addresses) as a single route update, and you will find that a lot of routes are aggregated even further than this (right up to /8s or 65K addresses per prefix).
Over time as the Internet grows, route-deaggregation (eg: taking a larger prefix and breaking it into smaller ones) has caused the number of required Internet routes to grow, and consequently the hardware requirements for holding the table have increased.
As of today (May 2018) there are 717,613 prefixes being advertised, which can be comfortably stored by a router with 2GB of memory with enough left to run the Router OS as well.
If you're interested, I recommend reading through https://www.cidr-report.org for up-to-date prefix counts and aggregation reports.