You should first get your terms straight. What you want is probably NOT a "refi" which is generally a NEW mortgage with an existing or different lender. Refi involves fees just as a new mortgage would. Generally a refi will NOT help some one in a situation like yours.
What you need is a "recast" or loan modification.
Recasting Your Mortgage The idea is that the EXISTING lender will realize that the rates you have are much too high, and quite probably the principal amount is far above the true value of the property. Lenders are much more likely to allow modification to the rate and terms than they are to the principal amount, though there are a handful of people that have been successful.
The keys are to have your ENTIRE financial picture ready to lay out for the lender. This includes the values of other comparable homes in your neighborhood so that the lender realizes that if they were to foreclose on you they WOULD NOT make any money. You have to find some one with the authority to realize it is NOT in the bank's best interest to do anything other than adjust your payments to something that will be affordable by you.
Good Luck!