How should I redo my patio under my deck?
Without seeing a photo of the scene I'd assume that you can put temporary legs in place. I'd install appropriate lumber at a slight angle to just outside of the patio area so that you can work on it unobstructed. 


Use something like a pair of 2x6 boards screwed together in a T configuration. This should give you the strength and stiffness necessary. 


Plan view:

 _________
|_________|
    | |
    | |
    | |
    |_|



Place large blocks under the posts to prevent them from sinking into the soil. 
Drive large steel or lumber stakes into the ground to anchor the temporary post legs. 
Anchor the tops of the posts to the beams such that they won't slip out. This could involve lapped lumber scabs screwed to the posts and the beam. 
Raise the beam slightly from its original position to allow easier installation of the new posts. 
Block all access to the deck while the project is underway. Check the security of the temporary posts frequently. A collapse could kill. 


How you repair or replace your patio is your prerogative. That part of the question is off-topic as either too subjective or unclear, given the few details you've provided about your ultimate goal.