This depends on what you mean by a gelatin "substitute".
What you have to understand is that while most hydrocolloids have gelling and stabilizing properties, they are not simply interchangeable. You can't substitute one of them 1-for-1 where you need gelatin and expect everything to just work.
A great place to start would be the Hydrocolloid Recipe Collection which, despite its name, is almost more of a cookbook, because it has detailed information on the properties of each hydrocolloid.
Agar is actually a stronger gelling agent than gelatin in the sense of having to use less of it to get the same strength, but you need to use it properly. The most important property of agar is that unlike gelatin, which gives hydration at temperatures as low as 50° C, agar requires a temperature of 90° C. In other words, you need to heat the water all the way to a rapid boil before the agar will actually "activate". A light simmer is not enough.
The other notable property of agar is syneresis, which is the loss of moisture over time. Agar sets extremely fast compared to gelatin and above room temperature, but unless you combine it with a small amount of Locust bean gum, it will actually dry out. Otherwise, though, you can absolutely, definitely substitute agar-agar for gelatin if you actually get pure agar (I made the mistake of buying the "dessert agar" once, which is not the same thing) and hydrate/set it properly. In fact, the biggest concern with using agar as a substitute for gelatin is that you might end up with something too stiff, since gelatin produces a much softer gel.
Perhaps the closest hydrocolloid to gelatin in terms of its properties is iota type carrageenan. Here's a side-by-side comparison of the most important characteristics (this is all taken from the HRC):
Property | Gelatin | Carrageenan | Agar
------------------+-----------+-------------+---------
Thermoreversible | Yes | Yes | Yes
Strength | Soft | Soft | Hard
Elasticity | Elastic | Elastic | Brittle
Shear Thinning | No | Yes | No
Hydration | 50° C | 70° C | 90° C
Setting Temp. | 15° C | 40-70° C | 35-45° C
Setting Speed | Slow | Fast | Fast
Melting Temp. | 25-40° C | 45-80° C* | 80-90° C
Viscosity | Low | Medium | Low
Gelling Conc. | 0.6-1.7% | 1.0-1.5% | 0.2%
Syneresis | No | No | Yes
You should be able to see by this how much closer carrageenan is to gelatin; trouble is, it's difficult to find, and you have to get the right kind (the kappa type and other types have very different properties).
There's actually an even better type of carrageenan to use a gelatin substitute, if you can find it: It's called Ceambloom 3240 and it's specifically designed to be a gelatin replacement.
I'd like to also note for the record that the answer in your ochef link is not really appropriate for gelatin desserts that need to hold their shape. Xanthan gum is a fantastic and versatile hydrocolloid but (to the best of my knowledge) it does not "set" the way that gelatin, agar, or carrageenan do. It's more of a thickener/emulsifier/stabilizer, at its highest concentrations being used to produce foams (but not gels). It's often used to stabilize other gels/foams but I've never heard of it being used to create a gel on its own.
Guar gum is also largely just a thickener, that you could use a stabler replacement for corn starch or arrowroot, which is also mentioned in that answer. None of these are appropriate at all for gels (desserts), they are only useful as thickeners.
To me, the definitive guide to all these gelling agents is "Texture", the free e-book at khymos.org (which I know about because of this site, by the way). It says that mango is an inhibitor to the working of gelatin, so gelatin won't help as much as you might hope. Having said that, some of the example recipes do use gelatin, so it might still help enough.
About guar gum, it says that acidity (low pH) is an inhibitor; are there any acids in your mango puree? It also says that guar gum leads to high viscosity when warm and low when colder, so cooling it down should definitely make things more solid. You could also try some of the other agents; maybe xanthan gum will help.
Best Answer
So, there are 2 problems with the possible solution of agar clarification:
1) Agar clarification (as far as I know) does involve heat to melt the agar and keep it melted - and usually you dissolve the agar IN the juice without any solvent, so, if you're going to heat up your juice enough for it to clarify, you're going to heat it up enough to break the proteases down. Bottom line, just boil the juice for the proteins to denaturate and save the money from the agar.
2) Proteases are very small protein chains and are unlikely to be completely removed by agar clarification. This process works because the agar "drags" the large molecules (like cellulose, etc.) and solids from the juice during the solidification process. You might remove some of the ficin, but not much. Also, issue #1 makes this answer redundant if you're not liking the idea of boiling your fruit...
Although, since your objective is to make some kind of solid from the fruit puree, why don't you use the agar itself to make the gel? You can use a small portion of the fruit juice/puree and then add the remainder later.