Here is a report of the last journey of Concorde from JFK-LHR, which mentions "The highest altitude we reached was 58000 feet." Is this height aerodynamically feasible to reach?
Yes. The extra height was necessary in order to reach lower pressure air, and thereby reduce drag, and heating of the airframe from supersonic compression of the air.
Concorde's windows were extra small, so that if a window did blow out, the air compression system could actively compensate by pumping air in faster than it could escape, until the pilot completed his emergency descent.
More details can be heard on this podcast.
Yes. According to Wikipedia, Concorde's service ceiling was 60,000ft.
The density will go down a bit at that altitude compared to normal aircraft, but your airspeed is Mach 2, so that's good. Lift is (among others) a factor of both parameters. Be aware that there is a bit more going on though with supersonic stuff as well.
An increasing number of aircraft are approaching this altitude domain. For instance, the subsonic corporate Gulfstream G650 tops at 51,000ft.
As per its service celling that would not have been an issue. It should also be noted that Mach 1 (the speed of sound) is about 90 Knots Slower at that altitude.