Here is a constructive proof that it is possible. It produces some pretty skinny and twisty regions that look like plasticene, though; @whuber's alternative solution in the comments will produce round blobbly regions that look like bubbles.
Enlarge the map uniformly so that every region is at least as big as its desired area. Now you just need to shrink the regions while maintaining adjacency. Pick a region $R$ whose area needs to be reduced. Find a connected sequence of regions $R, R_1, R_2, \ldots, R_n$ such that $R_n$ has a boundary with the outside space. Shrink $R$ to its desired area by "pulling in" its border with $R_1$ while keeping the endpoints of the border fixed, so that the topological adjacencies between regions do not change as shown below. This has increased the area of $R_1$, so for $i = 1, 2, \ldots, n$, restore $R_i$ to its original area by pulling in its border with $R_{i+1}$, or with the outside when $i=n$, in the same way. Thus you can reduce the area of any chosen region $R$ without changing the areas of the other regions, nor the adjacencies between regions. Repeat for all the regions that need shrinking, and you're done.
Below, for example, we reduce the area of region $A$ using the sequence $A, B$.
