Step 1) make your Paladin focus on Strength and Wisdom over Charisma (possibly Con and Dex over Cha, even).
2) Take the Two Weapon Fighting Feat and the Two Weapon Defense feat
3) Take the Ranger MC feat, and any other MC feats that give you useful powers. Notably, you can avoid the level 9 Paladin powers, which would require investing in Charisma to be of any use. Melee Rangers run on Strength and Wisdom, which you have in good measure.
Alternate number 3) Take the fighter MC feat, and then take appropriate MC feats to take Tempest powers from Martial Power. Fighters need a good Strength and can benefit from your good Wisdom as well.
optional 4) take a Double Weapon from Adventurer's Vault.
The aforementioned "play a Tempest fighter who works for the church" is actually a viable alternative. Don't assume that your holy warrior needs to be a paladin: a Fighter with a decent Wis score, and an MC feat into Paladin or Cleric could fulfill the "holy warrior" character concept just fine.