Does my choice between 32 and 64 bit make a significant difference? I'm always tempted to choose 64-bit options, but sometimes that seems to cause issues.
Does not matter nowadays. All of the modern MinGW builds are dual "multilib" and capable of producing both 32 and 64-bit executable. Bitness of MinGW build indicates which one is default but you always can force another by adding -m32/-m64 compiler switch to the command line.
Will the installation from that alone be enough for a fully functional mingw?
Normal MinGW installation should be self-sufficient. However, try not to keep multiple copies unless you know what you are doing. MinGW installation is perfectly usable as long as its 'bin' subfolder is in the PATH, but having multiple compiler builds in the PATH at the same time may screw things up.
Edit: a fully functional MinGW will not be enough to build libtcod, you will also need Cygwin.
I tried using it with MSYS grabbed from the older mingw folder, but it seemed to be missing important things.
I'm not sure what you call MSYS exactly (the definition of this component is a bit vague) but I strongly suggest you do not mix parts of different builds. If not sure, remove everything and unpack a fresh copy.
Don't make it too complicated. Install Code::Blocks with mingw (you should learn to use IDE) or Visual C++ free edition.
Code::Blocks does not rely on compiler to be bundled with it. It has builds with MinGW included (right now it is TDM 4.7.1 and 4.8.1) but I think knowing the line between the IDE and the compiler may help a lot. As far as I can tell, we are not doing "hello world" here.
Visual Studio Express for Windows Desktop (that is how free Visual C++ is called nowadays) is a valid choice too. If anything, it has awesomely integrated debugger. It is very different though, with its own rules, quirks and bugs. And I may be a bit on the subjective side, but I believe that starting from Dev-C++/Code::Blocks/Eclipse + GCC will be better in the long run.
However, none of the alternatives mentioned above would fix the original problem about linking with libtcod. Yet they might have made fixing it harder. Maybe I'm missing something, but as far as I can see libtcod has very unfriendly building mechanics. It practically requires MinGW with Cygwin, because versions newer than 1.5.1 have only makefiles and those makefiles rely on unix utilities.
Then, if some crappy library doesn't work, don't use it.
Yeah, use BearLibTerminal: linking is trivial, supports both MinGW and Visual C++ and does not require any recompiling :-P.