Q:

How to comprehensively test software that doesn't play well with testing?

I'm currently working in a project that aims to implement automatic testing of a software package. You can imagine this software is a bit like Excel in that it has a workspace that contains all the data, and a user interface that executes code that works on this workspace data. We are primarily focused on testing "core functionality", rather than the user interface in itself. Previously, a lot of testing has been manual and poorly documented.
One of the problems we're facing is that essentially anything that you might want to test requires a "complete" data set. Due to inherited architectural complications it is not really feasible to unit test anything - the mocking required is too extensive.
Another problem we're facing is that the code is in several different languages - mostly Python and C++. Some of the Python code is being run inside a Python interpreter running in the software, giving it access to C++ code that is otherwise less accessible.
Also, the current level of manual testing is deemed "good enough", and we aim to get at least "the same coverage". However, since manual testing inevitably goes through the UI and since the current manual cases are extremely poorly documented, who knows what we're currently covering with the manual tests?
I'm having a hard time understanding how to achieve good coverage (or even just how to measure coverage intelligently).
A lot of the standard answers I've come across so far don't really apply here. E.g., "write testable code" is a great tip when you start writing code, but refactoring millions of lines of code accumulated over 25 years is not in scope for this project, not a manageable task for a small team, and a political impossibility given the circumstances.
I'm looking for any and all suggestions on how to achieve good test coverage, how to measure coverage, and generally how to tackle the transition from poorly documented manual testing to some sort of sensibly comprehensive automatic testing.
I'm not an expert, so there may be low hanging fruit that I've overlooked, in particular if I happen to not know the relevant search terms - if that's the case, a gentle prod in the right direction may very well be a good start.

A:

I'm afraid there is no easy solution. "write testable code" really is the only way to do it.
Writing testable code is non-trivial, and retro-fitting tests is hard. Many of the advances in modern coding have been aimed at making code testable, with other benefits as a secondary effect. Writing the tests is the easy bit!
MrSmith's comment is a good strategy:

whenever a peace of code is extended/refactored/added/fixed add tests for this part. Over time you will improve the test-coverage this way step by step. 

This has a few benefits:

You don't need to argue with the doubters over whether it's worthwhile rewriting functional code.  
It targets tests at areas that are most important.  
You were already going to spend time testing these areas.  
There's no risk of your refactoring breaking an area that was otherwise unchanged. 

A:

You are not alone
Though a redundant mention, anyone reading this question while not having this kind of trouble ought to remember that real-life software development is full of cases of multi-year sub-standard development carried out under much time pressure, resulting in messy code-bases, which, nevertheless, superficially provide everything that has been practically requested. When life hands you over-25-years-of-accumulated-code with no tests, running away is not always an option.
All you have at the moment is your manual tests. While you cannot "magically" find out what they cover, you must free yourself of the time spent manually testing, which is probably better spent documenting (or improving, or writing actual tests).
If your only usable "framework" for testing is the actual User Interface, I suggest looking into GUI testing, which is, practically, based on "simulating" what you do when you are using the software. So, you can generate clicks here and there on the various UI elements in the order that you know a manual tester would. You may have to overcome problems such as automatically loading your dataset or setting options, but, depending on the code-base, you may be able to achieve this in the end.
Although this strongly depends on your current GUI framework, so it may be easier or harder to achieve, I believe an initial attempt at automating your current testing methodology might save you some time and even let you write new automated "manual" tests. Take a look here for a list of GUI testing tools to get a brief idea of what is around.
Apart from all that, Robin Bennett's answer is very good and timeless advice indeed.
EDIT:
Maybe a "shot in the dark", but if things are very hard, I think I have come across something that might be of assistance. Like I said, one of the only things that can help as to what is being tested, would be a continuous call stack trace... It might be possible that Valgrind's tool named callgrind, a callgraph analyzer (as per Wikipedia), might be useful for that reason. The tool describes itself as:

Callgrind is a profiling tool that records the call history among
  functions in a program's run as a call-graph. By default, the
  collected data consists of the number of instructions executed, their
  relationship to source lines, the caller/callee relationship between
  functions, and the numbers of such calls. Optionally, cache simulation
  and/or branch prediction (similar to Cachegrind) can produce further
  information about the runtime behavior of an application.

Sounds promising and, in the absence of any other better alternative, I would suggest giving this (or any other similar tool) a shot! A detailed call graph "trace" captured during each UI-based test would make it possible to discover what exactly is actually going on behind the scenes.
(Special reference goes to this answer, which pointed me in that direction).

