There is this whole Computer Sciences way of doing that, O-notation etc... but it is largely theoretical and concernes with algorithms, not tasks.

What do you mean by "estimate complexity"? It's one thing to look at complexity in the abstract sense (e.g. it takes N^2 operations on N items).

Task like 'create user' is numerically trivial, but may be extremely time consuming when you're talking to Active Directory.

It sounds like you're asking about how to analyze how much time a task takes (or many tasks take).

"Tasks" are not trivial. Tasks such as creating a user make use of algorithms (such as searching or sorting), so the traditional analysis applies. If anything, they are more complex, because you'll have to consider CPU and memory load, on the machines running the task, as well as network usage. Factor in the time of day. Even the degree of disk usage and fragmentation may affect how well a certain task runs.

How can I estimate if I'm at all able to accomplish something like 'Create Interface Module For Loudmouth Library'?

that would require using Inline::C or h2xs, following on that question, how do they compare in terms of required knowledge and free time?

I'm not sure what you mean by this. You want to create a module that does what?