some buying the right head unit

Thats really up to you and your preference/budget.

However.....if you are doing as you stated and using a dedicated amp for subs and another 4ch. for mids/highs IMO you should look for a deck with 3 sets of preouts...one set for front..one for rear..and one for sub..which should be adjustable. This will give to alot more control over the system at the deck. (fading/sub level/cross over points etc)

If you use a deck with just one set of rcas you can still do it..but it will be a "set and forget" system once the  adjustments are made at the amps other then volume and tonel adjustments at the deck.

Does the 4 channel amp have an RCA output? If it does then you can still use your HU. Connect the front and rear RCA's from your HU to the 4 channel amp, then connect the output from the 4 ch. to the input of your sub-amp. If your 4 ch. amp does have the RCA output (they usually do...) and you don't want to spens too much on a higher-level HU, then get a decent HU with front and rear RCA outputs and do this. Now, you may be able to find one with 3 sets. It all depends on how much you want to spend, but mostly it all depends on where you shop from.

Yes..that is another option..but....you will sacrafice sub level and crossover control at the deck, but will retain fader.

But if your sub amp has a remote level control...you can make up for that.  If not you need to decide what you are willing to sacrafice to save a few bucks..it's all wasted money if you are unhappy..or realize you should have done it right the first time... so keep that in mind.