"At least it is possible that we tried" - This mix of tenses is confusing. It is possible (in the present) that we tried (in the past). That means that it is possible we already did something in the past, but that we don't know whether we did it or not.
Why 'although'? 'Although' isn't necessary unless what follows is contrary to the idea that came before. What are we making an exception to? The 'Still' at the very beginning already establishes that this excerpt is contrary. It's not clear what you're contradicting within the paragraph.
The first one is the most grammatically correct.