Is believing a work, or not a work?
Well, according to Jesus, belief is a work.
28 Then they said to him,
“What must we do, to be doing the works of God?”
29 Jesus answered them,
“This is the work of God, that you believe in him whom he has sent.”
It may be tempting to try to reconcile this verse by declaring that belief is a work that God does and not work from God required for us to do, however, that's not really sustainable given the context. The crowd asks "what must we do to be doing the works of God?" And not "what must God do for God to be doing his own work?" Jesus actually answers their question directly. The work of God that they must do is to believe in the one whom God has sent. Here "belief" is a "work" as described by Jesus.
How do you reconcile Rom. 4:2-5 with John 6:28-29?
It seems that in order to spot the contradiction between Romans 4 and John 6, the OP read Romans 4:2-5 the following way:
Romans 4:2-5 2 For if Abraham was justified by works [at all], he has something to boast about, but not before God. 3 For what does the Scripture say? “Abraham believed God, and it was counted to him as righteousness.” 4 Now to the one who works [at all], his wages are not counted as a gift but as his due. 5 And to the one who does not work [at all] but believes in him who justifies the ungodly, his faith is counted as righteousness,
Instead, the passage should be read along the lines as follows to maintain internal and external scriptural consistency:
Romans 4:2-5 2 For if Abraham was justified by [all legally required] works, he has something to boast about, but not before God. 3 For what does the Scripture say? “Abraham believed God, and it was counted to him as righteousness.” 4 Now to the one who works [all that is required by contract/law], his wages are not counted as a gift but as his due. 5 And to the one who does not work [all that is required by law] but believes in him who justifies the ungodly, his faith is counted as righteousness,
This interpretation is required to have a meaning consistent with the surrounding context found in Romans and in the storyline of the examples used of Abraham and David who certainly did great works before God but could never perfectly fulfill all the legal terms of God's law contracted with Abraham and his descendants and with humanity at large. When understood this way, there is no conflict with there being some work required to gain access to all the righteousness of Jesus Christ who actually did all the legally required work that no one else could do. There is no conflict with God requiring some work that we do, to access the grace that covers us for all the work we don't do.
The Long Answer on How to Interpret of Romans 4:2-5:
Let's begin with acquainting ourselves a bit with the context within which this discussion of works and belief occurs.
The first time that Paul explicitly addresses works and justification is in the immediately prior chapter:
20 For by works of the law no human being will be justified in his sight, since through the law comes knowledge of sin. -Romans 3:20
Contextually we see that Paul is not talking about works in general, but specifically about works of the law. And, contextually, when he is describing the law, he is referring to the old testament law / terms of the covenant:
28 For we hold that one is justified by faith apart from works of the law. 29 Or is God the God of Jews only? Is he not the God of Gentiles also? Yes, of Gentiles also, 30 since God is one—who will justify the circumcised by faith and the uncircumcised through faith. -Romans 3:28-30
You see the major friction point that Paul was trying to address was the conflict between Jew and Gentile and for Paul the major dividing line was the set of legal requirements of the Jewish law exemplified most notably with regard to the issue of circumcision.
11 Therefore remember... you Gentiles in the flesh, called “the uncircumcision” by what is called the circumcision... 13 ...have been brought near by the blood of Christ. 14 For he himself is our peace, who has made us both one and has broken down in his flesh the dividing wall of hostility 15 by abolishing the law of commandments expressed in ordinances, that he might create in himself one new man in place of the two, so making peace... -Ephesians 2:11-15
The issue of the Law and circumcision is such a huge issue it spans at least 4 books of the New Testament (Galatians, Romans, Acts, and Ephesians). It seems that the problem with the unbelieving Jews is that they no longer had faith in God but their faith was in the works of the law. This became obvious for when the Word of God came to transition them from the old covenant to the new they kept the old covenant and rejected the Word of God.
It's important to understand that Paul is talking about the old testament law to understand the smooth transition between Chapter 3 and Chapter 4:
31 Do we then overthrow the law by this faith? By no means! On the contrary, we uphold the law. What then shall we say was gained by Abraham, our forefather according to the flesh? -Romans 3:31-4:1
What may seem like an abrupt introduction of a new subject is actually a continuation of Paul's discussion of upholding the Law. Here, when referring to the law, Paul is referring to the Torah, the first five books of the Old Testament in its entirety. He transitions to Abraham because his story is a perfect foil to the works of the law ideology since his subversive story is both revered by the Jews and is contained within the Law itself. The Jews were focused on the law of Moses, but Paul wanted them to look not just at the law of Moses, but the entire Law, the Torah. The law of Moses is only one part of this greater law collection. He is not talking about the law in general and works in general, but the Old Testament law and the works required by it.
With the preliminary context out of the way we are in a better position to understand the verses in question:
Romans 4:2-5 2 For if Abraham was justified by works, he has something to boast about, but not before God. 3 For what does the Scripture say? “Abraham believed God, and it was counted to him as righteousness.” 4 Now to the one who works, his wages are not counted as a gift but as his due. 5 And to the one who does not work but believes in him who justifies the ungodly, his faith is counted as righteousness,
Here Paul switches from talking about the "works of the law" to just talking about "works", however, when he refers simply to "works" he is still actually talking about the "works of the law" or the works legally required by the covenant contract. He continues to use "works" as a shorthand for works of the law. We can see this by focusing for a moment on verse 5 where it says "And to the one who does not work but believes in him who justifies the ungodly, his faith is counted as righteousness":
Now the idea that Abraham had done no work at all prior to scripture stating, “Abraham believed God, and it was counted to him as righteousness”, is not sustained by the scriptures. Such an idea might be sustainable if the phrase "“Abraham believed God, and it was counted to him as righteousness” occurred when God first made the promise to Abraham in Genesis 12:1-3.
Now the Lord said to Abram, “Go [literally a command to walk] from your country and your kindred and your father's house to the land that I will show you. 2 And I will make of you a great nation, and I will bless you and make your name great, so that you will be a blessing. 3 I will bless those who bless you, and him who dishonors you I will curse, and in you all the families of the earth shall be blessed.”
But the phrase, “Abraham believed God, and it was counted to him as righteousness” did not occur in Gen 12:1-3 when Abraham first believed God. But in Genesis 15:6 well after the events in Genesis 12 where Abraham walked over 500 miles simply because God told him to.
4 So Abram went, as the Lord had told him, and Lot went with him. -Genesis 12:4
In fact, if Abraham had not obeyed God, as he did in Genesis 12 walking over 500 miles to get to the promised land, it is hard to imagine that Genesis 15 would have ever taken place. This literal walk, by Abraham, is specifically referred to by Paul when relating to our spiritual walk of faith.
11 ...The purpose was to make him the father of all who believe without being circumcised, so that righteousness would be counted to them as well, 12 and to make him the father of the circumcised who are not merely circumcised but who also walk in the footsteps of the faith that our father Abraham had before he was circumcised. -Romans 4:11-12
For Paul, being a child of Abraham requires humans to take obedient actions (footsteps) in accordance with their faith. Indeed Paul saw the purpose of his apostleship was to bring about the obedience of faith among all nations:
Romans 1:5 5 ...we have received grace and apostleship to bring about the obedience of faith for the sake of his name among all the nations.
Far from involving no human effort whatsoever, for Paul, sincere faith involves obedient work just as the author James discussed:
14 What good is it, my brothers, if someone says he has faith but does not have works? Can that faith save him...? 17 ...faith by itself, if it does not have works, is dead... 26 For as the body apart from the spirit is dead, so also faith apart from works is dead. -James 2:14-26
So, Back to Romans 4:3, when Paul says "And to the one who does not work but believes in him who justifies the ungodly, his faith is counted as righteousness" he cannot mean that Abraham took no active work at all in the manifestation of his belief. . Instead it means something else which we can infer from the following verses.
5 And to the one who does not work but believes in him who justifies the ungodly, his faith is counted as righteousness, 6 just as David also speaks of the blessing of the one to whom God counts righteousness apart from works:
7 “Blessed are those whose lawless deeds are forgiven,
and whose sins are covered;
8 blessed is the man against whom the Lord will not count his sin.”Romans 4:5-8
Here we see that the idea of work is still scoped to the works of the Law. In this context to have righteousness counted to you apart from works is to have your lawless deeds forgiven. The concept of 'not working' is equated to the concept of committing lawless deeds and sin. In other words to not work means to fall short of God's law. If you fall short in any area of the law, you fall short of the whole law and you did not complete the work of the Law. No matter how much you did you did not do the work required. 'Not working' the way Paul is using it, doesn't mean that you do no works at all, but that you do not complete all of the righteous requirements of the law in its entirety.
We can see how the concept of righteousness apart from works means righteousness apart from completing or fullfilling the works of the law. This becomes more clear as we apply Paul and David's words to David's own life. In doing so, let us consider how the scriptures describes David:
David did what was right in the eyes of the LORD and did not turn aside from anything that he commanded him all the days of his life, except in the matter of Uriah the Hittite.
When David writes the words Paul describes as demonstrating righteousness apart from works, it is not the case that David was carrying out no work on behalf of God. In fact, David was very careful to carry out the commands of God except when he didn't. So again, having righteousness counted to you apart from works does not mean you do no work at all. It just means you do not do all the work equal to the righteousness counted to you.
The term, "And to the one who does not work but believes in him who justifies the ungodly, his faith is counted as righteousness", when applied to David cannot mean that David did no work for God, but that righteousness was counted to David beyond the work that he did to include the work that he did not do. David, fell short of all the work required by law and so did not fulfill or complete the works of the law and yet he was credited as righteous because of the grace of God and his obedient faith.
So now, paying attention to the context we see nothing is meant by Paul that is anything like a person is justified if they do absolutely no work or with no work involved. Such a position is not sustainable when we actually examine the two examples of the men Paul uses to illustrate what he's getting at. Therefore, there is no contradiction between belief being a work in John 6 and, in Romans 4, faith being credited to Abraham as righteousness without works, once we understand that what Paul means is that righteousness was credited to Abraham without doing all the required works of the law. Righteousness is credited to us beyond the work that we have actually done to include, by grace through faith, all the works covenantly required by God that only Christ could completely fulfill.