Oversampling then filtering and downsampling
As you've figured out, for the filter specifications you gave, you need a very high filter. To summarize, you're asking for:

Passband edge: 30 Hz
Stopband edge: 32 Hz
Minimum stopband attenuation: 68 dB

The main determining factor for the filter order that you need to meet the specifications is the width of the transition band as a fraction of the sample rate. In your case, you want a transition band that is 2 Hz wide, at a sample rate of 4096 Hz. That's a very sharp transition!
A better approach is to perform the decimation in multiple filter stages that are cascaded in series. This allows you to meet the overall frequency response requirements that you have without using a single very-high-order filter. You need an overall decimation factor of 64 to be implemented by the cascade of filters. It can be hard to determine the optimal (in terms of total overall computations to apply the filters) arrangement of stages, but I would recommend the following approach as a start:

Stage 1: Design a filter with a passband edge at 30 Hz and a stopband edge of (512 - 32) = 480 Hz. Decimate the output of the filter by 8. Thus, at the output of this filter, you will have a signal sampled at 512 Hz.
You might notice that this approach yields some aliasing, as the transition band of the stage-1 filter is allowed to extend beyond the new Nyquist frequency of 256 Hz. However, this isn't a problem, because none of the aliasing occurs within the desired passband of the overall cascade. You're allowing some energy to alias through into what will become the stopband of stage 2, where it will be eliminated. Stretching out the transition band of the stage 1 filter allows you to save some computations, because the wider transition will require a lower filter order. Since stage 1 operates at the highest sample rate, this can be a significant benefit.

Stage 2: Design a filter with a passband edge at 30 Hz and a stopband edge of 32 Hz. Decimate the output of the filter by 8. Thus, at the output of this filter, you will have a signal sampled at 64 Hz with a 30 Hz passband.
While this is still quite a sharp transition band, it should be easier to design because the transition band width is a factor of 8 larger when expressed as a ratio of the filter's sample rate. In addition, the work required to apply the stage-2 filter is reduced further because it operates at the lower 512 Hz rate instead of 4096 Hz.


Using MATLAB's fdatool, the above specifications yield the following filters:

Stage 1: 29th-order FIR, 0.1 dB passband ripple, 80 dB stopband attenuation



Stage 2: 852nd-order FIR, 0.1 dB passband ripple, 80 dB stopband attenuation


I just used the default attenuation settings for illustration. You'll notice that with this setup, the second-stage filter is still quite complex. While I've used filters of this length before, it's likely that you might want to break the problem down even further to avoid such long filters. To do so, you would add more stages of decimation. For instance, you might try three stages of decimation by 4, or 6 stages of decimation by 2. The best way forward is dictated by your system's constraints, but you should see the idea of the approach.