Do we need recursion in programming language to solve any problem?
In short, to answer your questions:

(1) You can convert any recursive algorithm into its non-recursive form.

(2) As stated by the others, you have all the features you need.

Computational Power (Turing-completeness)

You probably know that you cannot solve any problem, for instance, the halting problem is undecidable. And so are many other problems, such as deciding whether an arbitrary formula in first order logic is provable. Thus, with today's knowledge on computability, even the most advanced computer/programming system imaginable won't be able to process every query even if all the data is available.

When assessing the computational power of languages, computer scientists often use the notion of Turing-completeness: 
If you can describe (and run) any Turing machine in your programming language, then it is Turing complete and can solve any problem which can be solved by a Turing machine.

To get a feel for Turing machines, I strongly encourage you to use a Simulator and try to solve some simple problems.

In particular, have a look at the syntax of the sample program in the Simulator, which should give you an idea of your minimal language.

Expressive Power and Minimality

When it comes to language design, expressive power is more important to me than the ability to solve any computable problem. Many useful domain-specific languages are not Turing-complete, but address specific problems very well.

However, equally powerful computational models such as the Lambda Calculus (functional programming) or the Pi Calculus (concurrent programming) show that you can have a very small set of elegant, composable language elements to construct larger systems, to be able to reason about their composition while having the computational power of Turing machines at the same time. Beautiful.

So if it is minimality you are looking for, take a closer look at the Lambda Calculus. 
Other noteworthy well designed minimal languages are:


LISP
Prolog
Smalltalk and in particular Self


Feel free to add more languages to your personal list (and please let me know ;)