Can adjustable constant current/voltage source be made with Arduino?
You are basically describing (if you add an inductor and a diode into the mix) a simple switching regulator.  That is, at its simplist, a PWM signal, some smoothing (inductor, diode, capacitor), and feedback.

Use the Arduino's PWM to switch a P-channel MOSFET in the voltage supply. That switched supply is then fed through an inductor, and then smoothed with a capacitor:







simulate this circuit &ndash; Schematic created using CircuitLab

M1 does the switching of the power to charge the rest of the circuit.  L1 + C1 smooths the PWM out giving a constant smooth (ish) voltage. D1 completes the circuit between L1 and C1 in one direction only keeping the charge in the right part of the circuit.

R1 keeps the MOSFET turned off when not being driven.

R2 is a very small "shunt" resistor (maybe 0.1Ω for example).

The size of C1 and L1 are determined by the switching frequency of your PWM and the current demands of the circuit.  The higher your switching frequency the smaller your inductor can be, The higher your current demands the larger C1 needs to be.

Reading A1 gives the output voltage of the circuit, so you can adjust the PWM (using PID would be good) to get a specific voltage.

Reading A0 and A1 and subtracting one from another gives you the voltage drop across R2. From that, you can calculate the current through R2 using Ohm's Law. You can then use that to adjust the PWM to give you a specific current.

Of course, you can't do both at once. You either have a constant current (during the first charging phase to bring the cell voltage up to 4.2V), and then switch to constant voltage until the current drops to around 0.3C.  For dead cells, an initial constant current phase of (IIRC) 0.1C can recover the cell.

Some important notes about lithium cells:


They explode (just ask Samsung), so take care. It can be good to do your experimenting with the cell contained within a fireproof container.
Lithium Ion and Lithium Polymer cells don't like being over-discharged, but as long as they haven't been reverse charged they can generally be recovered.
Cells that are used in a series pack and haven't been charged with a proper balancing charger may well have been reverse charged if the pack has "died".


The reverse charge thing is what actually kills a Lithium cell.  Basically, no two cells will have exactly the same capacity. If you have, say, three cells in series and you discharge the whole pack to below the recommended minimum, once cell will have less charge than the others. If that cell hits zero the current from the other cells will start flowing backwards through it, and that backward current causes copper crystals to deposit on the electrolyte layer between the electrodes. Those pierce the electrolyte layer and short the two electrodes together, and at that point the cell is dead. No amount of recovery charging will get it back, it's physically damaged. 

So in summary: 


A single cell that has been over-discharged by itself will generally be recoverable.
A series pack of cells that has been over-discharged may well have physically damaged one of the cells in the pack through reverse charge flow.





  Will Arduino be fast enough to control a MOSFET that will pump magic pixies into a capacitor to achieve steady value of voltage on said capacitor?


Sure. You should pre-condition your power so it is always within a tolerable limit (i.e., feed your solar panel power through a suitable 5V buck regulator to give a clean 5V supply). There will always be some latency in the circuit due to how long the inductor "resists" changes in the voltage. A typical Arduino takes ~100µs to sample an ADC. In this kind of environment, that time is negligible since it's generally much faster than a single period of PWM. You can't respond faster than one period of PWM anyway.


  When MOSFET is not saturated state it's resistance is high and a lot of power is wasted as heat. Would it be possible NOT to use PWM to control it, but instead to turn it OFF or ON each cycle to minimize power loss?


That's what PWM does. It's ON or OFF. On at the start of a cycle, then off part way through.  Yes, there is a brief period twice per cycle while it does the switching, but that will be minimal compared to the on and off periods. The losses from that switching will be negligible compared to, say, running a MOSFET as an adjustable resistance controlled from an op-amp with feedback from a current shunt (i.e., a linear regulator).