Is there any physical or computational justification for non-constructive axioms such as AC or excluded middle? I became interested in mathematics after studying physics because I wanted to better understand the mathematical foundations of various physical theories I had studied such as quantum mechanics, relativity, etc. 
But after years of post-graduate study in mathematics, I've become a bit disillusioned with the way mathematics is done, and I often feel that much of it has become merely a logical game with objects that have no meaning outside of the confines of the game; e.g., existence of enough injectives/projectives, existence of bases for any vector space, etc. 
I am not really an applied person---I love abstract theories such as category theory---but I would like to feel that the abstractions have some meaning outside of the logical game. To me it seems that using non-constructive proof techniques divorces the theory from reality.
Essentially, my question boils down to the following:


*

*If I adopt a constructive foundation (like say an intuitionistic type theory), is there any (apparently) insurmountable difficulty in modelling the physical universe and the abstract processes that emerge from it (quantum mechanics, relativity, chess, economies, etc.).  

*Is there any physical/computational justification for assuming excluded middle or some sort of choice axiom? 
 A: You may want to look into Solomon Feferman's explicit mathematics.  Here is a quote from a draft version of a planned book Foundations of Explicit Mathematics (I've emphasized one sentence that I think you'll find particularly relevant).

Explicit Mathematics is a flexible unified framework for the systematic logical study of 
  those parts of higher mathematics in which proofs of existence
  guarantee the 
  computability or definability by specified means of what is demonstrated to exist. It 
  would seem that such parts of mathematics must be relatively restricted, given the 
  ubiquity of existence proofs throughout modern mathematics for which no 
  method is 
  known, either in practice or in principle, to produce the objects asserted to exist.  Indeed, 
  the main parts of mathematics covered by the Explicit Mathematics framework are 
  referred to as constructive, predicative, and descriptive
  in the senses 
  that will be 
  described below, and each was originally pursued on philosophical grounds that 
  mathematicians for the most part have not found persuasive and too confining for the 
  purposes of practice.  What is not generally known and will be revealed in the 
  present 
  work through the logical analysis provided by our framework is that in gaining the 
  uniform explicitness of solutions one does not pay a great price in terms of both the 
  workability and mathematical reach of these approaches, despite their philosophical and 
  methodological restrictions.  In particular, a weak predicative system already serves to 
  account for all scientifically applicable mathematics in current use. Though the 
  constructive, predicative and descriptive approaches are the main parts of mathematics 
  with which this book is concerned, Explicit Mathematics has proved to be adaptable to a 
  variety of other contexts ranging from theories of feasible computation and finitist 
  mathematics to large cardinals in set theory, as will be described in 
  the
  final part of this
  book.

Most of the work that has been done on explicit mathematics has been mathematical, rather than on justifying the above claim that explicit mathematics suffices for applications to the sciences.  This is understandable, because even in physics, which is perhaps the most mathematical of the natural sciences, the practitioners are generally not too concerned with what they would probably regard as fussy details of extreme logical hygiene.  If a mathematical argument works, and yields scientifically useful results, the scientists are not going to care too much about whether some arcane (to them) axiom was used somewhere along the line.  Heck, physicists often don't care if their arguments are mathematically rigorous by any mathematical standards!  For example, they're not going to sit around and wait for mathematicians to resolve all the debates about the rigorous meaning of the Feynman path integral before they allow themselves to use it.
So if you want to convince yourself that a logically weak system is sufficient for science, you may have to do a bit more work than you may have hoped.  Fortunately, you don't necessarily have to wait for Foundations of Explicit Mathematics to be completed (if it ever gets completed).  You can start with Constructive Analysis by Bishop and Bridges.  This will show you how a constructive approach can recover most of the results of analysis that are used in scientific applications.  (If you're particularly worried about the law of the excluded middle, Bishop and Bridges are probably even more relevant for you than Feferman, since explicit mathematics uses classical logic—although care is taken to avoid the highly nonconstructive uses of excluded middle that are what bother constructivists the most.)
A: In ZF, you can explicitly define a well-ordering of the entire constructible universe — so the axiom of choice is the theorem of choice if you reject the existence of noncosntructible sets (i.e. adopt the axiom of constructibility).
You can even get the axiom of choice as a theorem or even a triviality in somewhat more constructive settings. For example, given a family of types $X_\alpha$, the translation of the proposition $\forall \alpha \exists x : x \in X_\alpha$ into dependent type theory via the propositions-as-types paradigm is precisely the type of choice functions for the family, and so the assertion that this proposition is true is literally the same thing as specifying a choice function.

In a universe without the excluded middle, one distinguishes between the set $\Omega$ of truth values and the set $\{ \bot, \top \}$ consisting of false and true. While predicates are generally $\Omega$-valued, one still likes to find $\{ \bot, \top \}$-valued predicates where one can, since they are nicer to work with.
One can appreciate this sort of idea even in a purely classical context. For example, consider the category of topological spaces.
If $S = \{ \bot, \top \} $ is a two-point space, define an "S-valued predicate" on a space $X$ to mean a continuous function $f : X \to S$. Any such function has a corresponding subspace $f^{-1}(\{\top\}) \subseteq X$.
If $S$ has the indiscrete topology, then $S$-valued predicate are the same thing as functions $X \to \{ \bot, \top \}$, so these are just boolean predicates on the points of $X$.
If $S$ is the Sierpinski space and $\top$ is the open point, then $S$-valued predicates correspond to open subspaces of $X$, and thus describe some sort of "open property" that respects the topology of the space. Alternatively, taking $\top$ to be the closed point gives a notion of a "closed" property.
If $S$ has the discrete topology, then $S$-valued predicates on a space $X$ correspond to a property on the connected components of $X$. While these predicates are less common, they tell you something very strong about the space.

My general philosophy on these things is very heavily influenced by the idea of an internal language — in particular the internal language of a topos, or more general categories.
So, while you might want to do some work in some weaker setting, the most expedient approach to the foundations is:


*

*Formalize of abstract mathematics in the way that's easiest to do work in

*Using this convenient ambient mathematical setting, define/construct the types of universes you want to work in, and develop their theory

*Flesh out the internal language of this universe 


As an example, you mention an interest in "intuitionistic type theory" — it turns out, for example, that (intuitionistic) dependent type theories = locally cartesian closed categories. If you also insist on a type of truth values, you get precisely the notion of "elementary topos".
For the purposes of doing classical physics where you've defined a (topological) state space, or at least hypothesized one without actually constructing one, then a particularly appealing construction is the topos of sheaves on state space.
The internal language of this topos allows you precisely express various ideas I've seen thrown about based on 'physical intuition'.
For example, the idea that "physical variables don't have exact values" can be expressed by observing you can have an internal real number (i.e. some real-valued physical observable)  $X$ with the property that $X = r$ is identically false for every ordinary real number $r$. In fact, this is a typical property for internal real numbers to have; $X = r$ will always be identically false unless there is some open subset $U$ of state space on which $U$ is constant.
A: Your question appeals to me in its clarity and relevance. I would love to give a similar clear answer, but as we stand in math and physics I believe that matters are not so clear-cut.
As pointed out in the comments above, no mathematics suffices to describe reality. But in physics we try nonetheless to describe parts of reality, and especially patterns that we believe to observe. For these patterns we also seek explanations in such a way that it helps us to delve deeper into the physical world. By delving deeper I mean that we gain more traction over the things we observe. For instance we now have 'access' to particle-physics processes, which enables us to study and observe yet more deeply the mysteries of the Planck-scale world.
Mathematics can also be seen as the science of patterns and (cor)relations. For physics, I believe it doesn't intrinsically matter which part of mathematics we use to describe a pattern, as long as the mathematical description fits our observations and helps us to gain more traction [I would like to say: 'helps us to gain more understanding', but history shows that what we in our time believe to be understanding will probably be labeled misunderstanding by generations to come...].
Now constructive mathematics offers a very beautiful and fruitful 'new' framework/perspective to look at the physical world. I personally believe that, in one very fundamental way, intuitionistic mathematics is more suited for physics than classical mathematics BUT...
in many other ways, classical mathematics offers the mind 'easy' approaches to explore new patterns and (cor)relations, precisely through not having to worry about feasibility, reality etc. This 'freedom to ignore boundaries' is very important I believe in ANY science, and I often find it distressing to see that unorthodox creativity and real originality have a hard time in our academic communities.
So, summarizing I would say that 
a) there are no insurmountable obstacles to phrase our current physics in intuitionistic mathematics, but it would need hard work to do so 
b) intuitionistic mathematics has a fundamental perspective to offer, both unifying and simplifying in nature, which I believe would go a long way in helping us delve deeper, so this work would be justified
c) it would be unwise to abandon classical mathematics for its ('unjustified') dreamlike abstractions, on the contrary we should embrace any mental dreams as long as they offer simplicity, beauty, mystery, etc. The drawback that I personally perceive with classical math in relation to physics is that the tacit acceptance of LEM and impredicativity often lead to mathematical machinery that is more complicated than necessary. And as I think to learn from history, simplicity and elegance are the gateway to progress in physics.
To answer your second subquestion: LEM plays an important role in so-called 'discrete' math systems in constructive mathematics. 'Discrete' then signifies that the equality of objects is decidable. For instance the algebraic numbers are a discrete subset of the complex numbers, and this gives a lot of constructive traction to 'constructivize' all sorts of classical theorems about the complex numbers. But in general of course LEM fails hopelessly. Certain choice principles are somewhat generally accepted in constructive mathematics, on the other hand most choice principles can be avoided by choosing careful definitions which incorporate the extra information necessary.

[Update 23 march to reflect the questions in the comments below:]
What I perceive as intuitionistic math's strong point for physics, is its insistence on potential rather than actual infinity. 
This one strong point results in
a) a very elegant way of dealing with data from measurements, since in INT (intuitionistic math) one does not see real numbers as completed (infinite sequences of converging rationals), but as a sequence of shrinking intervals, which arises over time and which is never finished, but which can be pursued to an arbitrary precision. 
b) a germane way of resolving one fundamental paradox in physics: is our world completely finite in all conceivable ways (which would be extremely hard to fathom) or is it fundamentally infinite in some way (which is equally hard to fathom...)
c) an interesting way of looking at (information) entropy since it implies that large numbers or large strings or whatever only arise over time...
d) a nice explanation why compactness might be a feature of the physical world (there is a sound math model called RUSS in which compactness fails, and I know of no good argument why classical math would describe the physical world better than RUSS...)
e) a nice explanation why physical processes are usually continuous, although this explanation becomes questionable at the Planck scale.
... well that should be enough for now.
In classical math, the main feature that I find very unpractical for physics is directly related to a) above. In classical mathematics we build the reals as equivalence classes of (say) Cauchy-sequences of rationals. But we never encounter equivalence classes when measuring/observing data. So it's very much like taking a lot of trouble to put your stuff in boxes (equivalence classes), and then each time you want to do something practical, you have to take everything out of these boxes again...
You may think that this is not so complicated, but for physics I disagree. When we look at the reals as arising from a pointfree setting, basically like Brouwer did and which is common in INT, then one gets a different intuitive picture of what is possible, for instance on the Planck scale, in terms of physical-world substrates underlying our measurements.
Basically, the whole idea of reals becomes simpler in the pointfree setting (well, if one takes care to simplify...) and to me this opens the mind for different avenues of exploration.
A: It depends on what you want out of your science!
If you want your relativity theory to include dramatic singularity theorems — then probably you will want excluded middle to prove them.
If you want your economics to use fixed-point theorems with short and conceptual proofs — then probably you will want excluded middle in those proofs.
But if what you want is predictions and calculations within specified error limits, then you won’t need excluded middle to do them: the arithmetic of rationals is decidable.
Similarly in chess, most of the instances of excluded middle that would occur to you will be constructively valid from the finitary nature of the situation.
So you can use examples from mathematical physics or mathematical economics in discussing constructive math. However, the existing modeling practices are diverse enough that they don’t provide a clear and non-circular justification for adopting or abandoning the logical principles at issue.
A: Not an answer, but an opinion.  The question whether it would be 
difficult to model physical phenomena using constructive mathematics would make some sense if those physical phenomena were modeled by mathematicians. Of course, it is not the case: this is a job for 
physicists and other scientists. 
My impression from reading physical literature so far is that, very rare cases aside, physicists could not care less about  mathematical rigor. 
Given this, I cannot see what difference for them would it make whether it is classical or constructive mathematics, so the above question is, at best, premature. (Although the situation may be different in other areas such as, for example, computer science.)  
