Editor's comments differ from those of reviewers I have recently received reviews for a journal paper I submitted a few months back. The verdict is a major revision (three out of four reviewers requested this, the fourth said accept with minor revisions).

Many of the reviewers felt like we did not justify our approach sufficiently, to which we agree and can improve upon. The editor; however, in their comments to us, stated that we should take a different (much more complicated) approach altogether (even though none of the reviewers suggested changing the entire approach, only to justify why we chose the approach we did).

Question: How should we proceed when the editor's comments seem much stronger than those of the reviewers? 

It is not feasible to accommodate the editor's requests by the deadline. I'm unsure if the reviewers made (stronger) private comments to the editor requesting larger changes or if the editor interpreted the reviewers comments much differently than we did. The paper will go back to the reviewers after we make the requested changes.
It's the editor's call, and since you have no right to get your manuscript published, you don't really have a basis to ignore the editor's request -- if that's what the editor wants, then that's what you likely have to give him/her.

That said, while the manuscript management systems most journals use typically give you a deadline by which you have to turn around revisions, these are not actually enforced. That's because if you need to, you can always let the deadline pass and submit your revision as a new paper -- if you mention in your cover letter that it is a resubmission of a prior manuscript, then it will go to the same editor and from that person likely to the same reviewers.

The better approach is to discuss the timeline issue with the editor. Email the editor back and state that you're looking forward to making the requested changes, but that you can't do it in the requested time. Ask whether you can get an extension, stating how much time you need. As an editor, I can't see a reason why that should not be granted.